Sequential threads are imperative functions that can be called in the Lucid
part of a GIPSY program. The data elements of a Lucid program are integers and
the like. Using them as such would result in a very inefficient computation
due to the overhead in generation and propagation of demands. STs overcome
this problem. The notion of sequential thread and granularization of data was
introduced by the GLU (Granular LUcid system [JD96, JDA97].

Figure 19: Hybrid GIPSY Program Compilation Process

Each GIPSY program potentially defines several Java methods that can be called
by the Lucid part of the program. Each of these functions are coded in the
Java part of the GIPSY program; thus, a sequential thread represents by itself
a bit of work to compute split into one or more Java methods. They are
compiled (see Figure 19) to Java byte code by the compiler (GIPC, Figure 10)
and packed into one executable, along with the Communication Procedures (CP)
(see Section 3.3.3.2) needed for the communication between the generator and
worker (Section 3.3.3.4, Figure 20). The notion of worker is thus very close
to the notion of sequential threads, where a worker is basically the
aggregation of the (potentially) several sequential threads that can be
executed by a worker, along with the communications procedures needed for the
generator-worker communication.

Notice that the Generator-Worker Architecture may well be extended so that the
worker and the generator are fused into one; this is under review and is
discussed in [Lu04] and in [VP05]. This gives us distributed generators as
outlined in [Gro02b], but as yet is only a topic for discussion.

#####  3.3.3.2 Java Communication Procedures

The functional demands (i.e., demands that raise the need for a Java function
call) are potentially computed by remote workers, upon demand by the
generator. The demand is sent via the network by the generator to the worker,
along with the data representing the parameters of this Java function call.
Sending this data through the network requires the breaking of the data
structure into packets transmissible via a network. This packing of the
demand’s input data is done by the Communication Procedures, along with some
kind of remote procedure call to the worker using, for example, TCP/IP RPC.
Once the function (the sequential thread) resolves, the worker (Section
3.3.3.4) is responsible for sending back the result to the generator that
called for this demand. That is also done by the CPs.

The CPs are generated by the compiler (GIPC) using the first part of the GIPSY
program: the definition of the data structures sent over the network (i.e.,
the parameter and return types of the Java functions). The GIPC parses these
Java data structures and translates them into an abstract syntax tree. This
tree is then traversed by the CP generator, which generates byte code for the
communication procedures, following the communication protocol that was
selected. Serialization summarizes much of this and Java helps us do it.

The CP generator has to be extremely flexible, as it has to be able to
generate code that uses various kinds of communication schemes. In a nutshell,
CPs determine the way a ST should be delivered to the computing host’s worker
depending on the communication environment. For the localhost, it is plain TLP
(i.e., we create Java threads on a local machine) so
NullCommunicationProcedure (Section B.2) is used. For distributed environment
CPs wrap transport functions over Jini, DCOM+, CORBA, PVM, and RMI (see [Lu04,
VP05]) protocols. Both CP and ST interfaces are presented in Section 4.1.1.8.

#####  3.3.3.3 C Sequential Threads and Communication Procedures with the JNI

This is the methodology of how to extend the Java ST/CP generation concepts to
C (and similarly can be done for C++) with the JNI [Ste05] introduced in
Section 2.6.1.2, page 2.6.1.2. This approach was designed, but not implemented
as of this writing; however, it may serve as a good head start on the
implementation of the CCompiler in GICF.

Much of the ST wrapper class generation code for C will be similar to that of
Java. The main difference is the bodies of the sequential thread functions
will not be present in the generated class as-is, but they will be declared as
native with no Java implementation. The C code chunks will be saved to a .c
file and the corresponding .h fill will be generated declaring all the needed
prototypes with the javah tool provided with the standard distribution of the
JDK. After that, we call an external C compiler to compile the C chunks into a
shared library. Thus, the other modification to the generated wrapper class
the CCompiler has to do, is to add a static initializer with the
System.loadLibrary() call for the newly compiled library with the C
implementation of our ST(s). The generated ST class and the compiled mini-
library can be stored together (e.g. the binary library file can be loaded
into a byte array of the class and deserialized back when about to be
executed) in the imperative node and later be communicated just like Java STs.
A more sophisticated alternative is to do the compilation and dynamic loading
after communication by the engine, but this can be a next step.

As far as type matching concerned, we still can use the same mapping rules
defined in Section 3.3.2 (and subsequently the TypeMap class of the
JavaCompiler presented later on) because with the JNI with still work with
Java and the JVM can do Java-to-native type translation to C or C++ for us,
not only for primitive types, but also for arrays, objects, and strings.

#####  3.3.3.4 Worker Aggregator Definition in the Generator-Worker
Architecture

The GIPSY uses a generator-worker execution architecture as shown in Figure
20. The GEER generated by the GIPC is interpreted (or executed) by the
generator following the eductive model of computation. The low-charge ripe
sequential threads are evaluated locally by the generator. The higher-charge
ripe sequential threads are evaluated on a remote worker. The generator
consists of two systems: the Intensional Demand Propagator (IDP) and the
Intensional Value Warehouse (IVW) [Tao04]. The IDP implements the demand
generation and propagation mechanisms, and the IVW implements the warehouse. A
set of semantic rules that outlines the theoretical aspects of the distributed
demand propagation mechanism has been defined in [Paq99]. The worker simply
consists of a “Ripe Function Executor” (RFE), responsible for the computation
of the ripe sequential threads as demanded by the generator. The sequential
threads are compiled and can be either downloaded/uploaded dynamically by/to
the remote workers. Better efficiency can be achieved by using a shared
network file system.

Figure 20: Generator-Worker Architecture

An example: a GIPSY screen saver would be a sample worker running when the an
ordinary PC is going into an idle mode and normally launches ordinary dancing
bears screensavers, it can actually run our downloaded worker instead and
contribute to computation. When such a worker starts, it has to register it
within a system somehow (see [VP05]), so that the generators are aware of its
presence and can send demands to it. In the event of merging of semantics of a
worker and a generator, such a screensaver would also be able to generate
demands and maintain a local warehouse.

###  3.4 Summary

This chapter presented methodology behind concrete implementations of the
first two hybrid languages in the GIPSY – JLucid and Objective Lucid. Semantic
rules were presented for free Java functions and Java objects to be included
into the Lucid programs and evaluated by the eduction engine in the hybrid
environment. Furthermore, operational semantics of Objective Lucid is clearly
defined and is compatible with the semantics of Lucid. The general
requirements for the GICF, a tool simplifying imperative compiler management
within GIPC, are introduced. The follow up chapter details the architectural
and detailed designs and concrete implementation of the languages as well as
General Intensional Compiler Framework and overall module integration and
their interfaces. Some immediate benefits and limitations are outlined below.

####  3.4.1 Benefits

  * •

JLucid opens the door for STs and CPs and first hybrid programming paradigm in
the GIPSY.

  * •

JLucid provides ability to either write Java code alongside the Lucid code or
embed existing one via embed().

  * •

Objective Lucid introduces Java objects and their semantics in the GIPSY.

  * •

GICF generalizes the embed() mechanism to all languages in the GIPSY.

  * •

GICF promotes general type handling in the GIPSY.

  * •

GICF promotes general compiler handling in the GIPSY.

  * •

GICF generalizes the notion of the STs and CPs for all compilers.

####  3.4.2 Limitations

  * •

JLucid is limited only to GIPL-Java and Indexical Lucid-Java hybrids.

  * •

JLucid does not allow Java objects.

  * •

JLucid restricts the embed() mechanism only to itself and its derivative –
Objective Lucid.

  * •

Objective Lucid is primarily an experimental language to research on Java
objects in the intensional environment.

  * •

GICF addresses mostly the imperative compilers, but a similar approach can be
applied to the intensional and functional ones.

##  Chapter 4 Design and Implementation

This chapter combines the architectural and detailed designs and integration
of the modules contributed not only by the author of this thesis but also by
the other GIPSY team members. Section 4.1 explores the GIPSY architecture and
implementation of the major components and frameworks. Then, Section 4.2
focuses on the user interface and external library interfaces. User
interfaces, class and sequence diagrams are provided mostly following the top-
down approach. For GIPSY Java packages, directory structure with description
of each package, and .jar file packaging please refer to Appendix C.

###  4.1 Internal Design

The GIPC framework redesign along with the realization of the two children
frameworks of GICF and IPLCF are presented first followed by the design and
implementation of JLucid and Objective Lucid integrated into the new
frameworks.

####  4.1.1 General Intensional Programming Compiler Framework

The GIPC Framework experienced several iterations of refinements as a result
of this research. Two new frameworks emerged, namely General Imperative
Compiler Framework (GICF) to handle all imperative languages within the GIPSY
and, its counterpart Intensional Programming Languages Compiler Framework
(IPLCF).

#####  4.1.1.1 General Imperative Compiler Framework

GLU [JDA97, JD96], JLucid [MPG05], and later Objective Lucid [MP05b] prompted
the development of a General Imperative Compiler Framework (GICF). The
framework targets integration (embedding of) different imperative languages
into GIPSY (see [RG05a]) programs for portability and extensibility reasons.
GLU promoted C and Fortran functions within; JLucid/Objective Lucid promote
embedded Java. Since GIPSY targets to unite all intensional paradigms in one
research system, we try to be as general as possible and as compatible as
possible and pragmatic at the same time.

For example, if we want to be able to run GLU programs with minimum (if at
all) modifications to the code base, GIPSY has to be extended somehow to
support C- or Fortran-functions just like it does for Java. What if later on
we would need to add C++, Perl, Python, shell scripts, or some other language
for example? The need for a general “pluggable” framework arises to add
imperative code segments within a GIPSY program. We could go even support
multi-segment multi-language (with multiplicity of 3 or more languages) GIPSY
programs. Two examples are presented in Figure 1 and in Figure 2.

    #funcdecl

    Integer f();
    void gee();
    void z();

    #typedecl

    Integer;

    #JAVA

    Integer f()
    {
        return new Integer("123");
    }

    #CPP

    #include <iostream>

    void gee()
    {
        cout << "gee" << endl;
    }

    #PERL

    sub z()
    {
        while(<STDIN>)
        {
            s/\n//;
            print;
        }
    }

    #OBJECTIVELUCID

    A @.d 5
    where
        dimension d;
        A = B fby.d (A - 1);
        B = C fby.d (B + f().intValue());
        C = z() && gee();
    end;

Figure 1: Example of a hybrid GIPSY program.

    /**
     * Language-mix GIPSY program.
     *
     * $Id: language-mix.ipl,v 1.5 2005/04/25 00:16:30 mokhov Exp $
     * $Revision: 1.5 $
     * $Date: 2005/04/25 00:16:30 $
     *
     * @author Serguei Mokhov
     */
    #typedecl

    myclass;

    #funcdecl

    myclass foo(int,double);
    float bar(int,int):"ftp://newton.cs.concordia.ca/cool.class":baz;
    int f1();

    #JAVA
    myclass foo(int a, double b)
    {
         return new myclass(new Integer((int)(b + a)));
    }

    class myclass
    {
        public myclass(Integer a)
        {
            System.out.println(a);
        }
    }

    #CPP
    #include <iostream>

    int f1(void)
    {
        cout << "hello";
        return 0;
    }

    #OBJECTIVELUCID

    A + bar(B, C)
    where
        A = foo(B, C).intValue();
        B = f1();
        C = 2.0;
    end;

    /*
     * in theory we could write more than one intensional chunk,
     * then those chunks would evaluate as separate possibly
     * totally independent expressions in parallel that happened
     * to use the same set of imperative functions.
     */

    // EOF

Figure 2: Another example of a hybrid GIPSY program.

#####  4.1.1.2 Generalization of a Concrete Implementation

Thus, the JavaCompiler component (see Figure 19), part of GIPC, has to be
generalized, and the JavaCompiler itself be a concrete implementation of this
generalization. The generalization would express itself by having an abstract
class ImperativeCompiler, the generic Preprocessor (vs. JLucidPreprocessor in
Section 4.1.2) should be able to cope with all PLs and know what PLs are
supported through enumerating them. Another thing the GICF buys us is an
ability to have any supported imperative programming language embedded in any
supported intensional programming language. Though this may seem impractical
at the first glance, but the framework is designed such that a lot of syntax,
semantics, and type mapping work is performed by the individual concrete
compiler implementations and not by the generic machinery. The goal here is
that as long as any given compiler within the framework conforms to the
designed interface specification and produces the required data structures,
there should be least possible effort to enable such a compiler in GIPSY.
Thus, the compilation process, semantic checks, linking, and execution at the
meta level of implementation of the GIPC and GEE can be reasonably generalized
without loss of practicality as we shall see. With this great deal of
flexibility, we have several issues:

  * •

Binary portability of compiled languages, such as C/C++ on a different host
(this problem theoretically does not exist for Java).

  * •

Though some languages, such as Perl, Python, shell scripts, are interpreted, a
version mismatch may happen.

  * •

A compiler for interpreted languages other than Java would be rather simple
because should we want to pass the ST code to a remote host, all we need is to
pass the source itself. Of course, in both compiled and interpreted variant
there is a large potential of security vulnerability exploits (e.g. with
malicious code injection), which will have to be dealt with as a part of the
future work. As of this writing, there are no embedded checks in GIPSY for
that; instead a guide of a sandboxed installation of GIPSY will be provided
when the system is released.

  * •

Another important issue is having imperative PL nodes in the AST. The issue is
in what such nodes should contain in order for them to be linked back into the
main AST, how to perform semantic analysis of the hybrid code based on the
contents of such nodes, and GEE should go about executing this code.

  * •

Various languages define their own set of types and typing rules, gluing them
all together is a very difficult task for semantic analysis and type
inference.

The follow up sections clarify and address most of these issues.

#####  4.1.1.3 Resolving Generalization Issues and Binary Compatibility

In order to fully support GICF, the original GIPC framework in Figure 3
(discussed in detail by Wu and Paquet in [PGW04]) has to be altered in the
following way: the Preprocessor has to be added on top of all the front-end
modules, and new links drawn between the Preprocessor and the other modules
Figure 4. This also changes the data structures flow between the components.
For the unaware reader, what follows is the brief description of the layers,
components, and abbreviations of the conceptual design present in Figure 4:

The front-end and back-end layers are the two bottom ones represent the main
machinery of the GIPC. The front-end compilers and parsers are responsible for
parsing, producing initial syntax trees, STs, and CPs. At this layer, the main
abstract syntax tree AST is always compliant to the one of Generic Intensional
Programming Language (GIPL). If the source code program was written in some
specific intensional programming language (SIPL, e.g. Indexical Lucid or
Tensor Lucid), its AST has to be translated first into GIPL. Both, GIPL and
SIPL type components may translate a Lucid dialect source code into a data
flow (DFG) graph language and back; hence, there is a variety of the DFG
translators. Next, the other two types of conceptual components at the front-
end layer are the data type (DT) and the sequential thread (ST) front-ends.
These correspond to the imperative language compilers and their modules in the
implementation. The DT front-end is responsible for analyzing data-type
definitions in the ST code and producing native (i.e. compiled) representation
of communication procedures (NPCs). The ST front-end is responsible for
compilation an ST code and producing some equivalent of the native compiled
code (NST) as the end result.

The GIPC back-end layer performs finalization of a GIPSY program compilation
by doing semantic analysis and eliminating Lucid functions and producing the
demand AST (DAST) along with linking in the generated STs and CPs from the
imperative side. The GEER generator then produces the final linked version of
a GIPSY program as a resource usable by the GEE (GEER).

The first two layers are meta-level layers that prepare information for the
front-end and back-end layers. The second layer is the GIPC Preprocessor layer
discussed in depth through the rest of this chapter. The top level has to do
with some language specification processing and creating corresponding parsers
and data structures for the front-end layer. SIPL and GIPL front-end
generators have to do with the fact that our SIPL and GIPL parsers are
generated out of a source grammar specification by javacc. Thus, a GIPL
specification corresponds to the GIPL grammar in the GIPL.jjt file and the
GIPL spec processor is the javacc tool. The DT and ST front-end generators
exist for the same idea as the GIPL and SIPL ones do. However, in the current
implementation they are not present either because they are hand-written or we
rely on the external compiler tools (e.g. javac to compile Java STs) to do the
processing for us. The design however implies that these components may
eventually be converted to the genuine imperative compilers within GIPSY
giving greater control and flexibility over the imperative parts than relying
on external tools. Therefore, we may acquire a Java.jjt one day, for example,
and generate a Java parser out of it.

Figure 3: Original Framework for the General Intensional Programming Compiler
in the GIPSY Figure 4: Modified Framework for the General Intensional
Programming Compiler in the GIPSY

###### Format Tag

To address some binary compatibility issues we invent a notion of a format tag
attached to the STs and CPs. The format tag’s purpose is to include meta-
information about STs and CPs such that it includes the programming language,
the object code format, the operating system, compiler, and their versions.
This is important if we are sending platform-dependent compiled code, such as
that of C or C++ from one host to another with different architectural
platforms. The FormatTag API is in Figure 5.

Figure 5: The FormatTag API.

We implement format specifications as a hashtable. We also predefine some
common format tags, such as JAVA, for conveniences as most frequently used.
The class overrides toString() and equals() of Object to define that the two
format tags are only equal if the string representation of all their
specifications are identical.

###### Sending Source Code Text

Not all non-intensional languages require compilation, e.g. Perl, Python, etc.
These can be sent over as plain source code text; thus, the format tag will
indicate the fact. We can go even further with this and send any language as
plain text and compile it on the target host instead prior invocation. For the
task of the source code inclusion we reserved the
SequentialThreadSourceGenerator. Of course, this won’t work for embed-included
binary code via a URI parameter because that code was already compiled by
someone else on some specific platform. As far as current implementation
concerned, the generated ST class does always contain the source code of STs
from the GIPSY program code segments, but it is unused by the GEE except for
debugging as of this writing.

###### Dictionary

The Preprocessor’s dictionary will initially be constructed based on the
#funcdecl and #typedecl program segments. The dictionary will serve as an
input to three other components: the NST generator (for error reporting and
pointers to the nodes in the AST and the compiled code), to the NCP generator
(to analyze the data structures used by STs and generate CPs accordingly), and
to the semantic analyzer, to perform data type matching between the
intensional and imperative parts. Both NCP and NST generators work under the
command of some imperative language compiler and are referred to as
SequentialThreadGenerator and CommunicationProcedureGenerator in their most
general forms, which are subclassed by a concrete language implementation.

#####  4.1.1.4 GIPC Preprocessor

The Preprocessor is something that is invoked first by the GIPC on incoming
GIPSY program’s source code stream. The Preprocessor’s job is to do
preliminary program analysis, processing, and splitting into chunks. Since a
GIPSY program is a hybrid program consisting of different languages in one
source file, there ought to be an interface between all these chunks. Thus,
the Preprocessor after initial parsing and producing the initial parse tree,
constructs a preliminary dictionary of symbols used throughout the program.
This is important for type matching and semantic analysis later on. The
Preprocessor then splits the code segments of the GIPSY program into chunks
preparing them to be fed to the respective concrete compilers for those
chunks. The chunks are represented through the CodeSegment class that the GIPC
collects. The corresponding class diagram of is in Figure 6.

Figure 6: The GIPC Preprocessor.

The Preprocessor can also be told to report certain code segments are invalid
at the preprocessing stage rather delaying the error until the compiler
discovery stage through the addInvalidSegmentName() and addValidSegmentName()
methods and maintaining internal vector of the strings with invalid segment
names. This feature is for example used in Preprocessor’s extensions of
JLucidPreprocessor and ObjectiveLucidPreprocessor later on that filter out
code segments that do not belong to the languages. The filtering logic works
like this:

  * •

if no valid and invalid segments are specified, all segments are accepted as
valid at the preprocessing stage. This is the default for general GIPC work.

  * •

if some invalid and no valid segments are specified, the Preprocessor will
error out on the invalid segments

  * •

if only valid segments are specified, everything else will be treated as
invalid

  * •

if both valid and invalid segments are present; the invalid set segments are
ignored and everything that it is not mentioned in the valid set is said to be
invalid.

###### GIPSY Program Segments

Here we define four basic types of segments to be used in a GIPSY program.
These are:

  * •

#funcdecl program segment declares function prototypes of imperative-language
functions defined later or externally from this program to be used by the
intensional language part. These prototypes are syntactically universal for
all GIPSY programs and need not resemble the actual function definitions they
describe in their particular programming language.

  * •

#typedecl segment lists all user-defined data types that can potentially be
used by the intensional part; usually objects. These are the types that do not
appear in the matching table in Table 1.

  * •

#$<$IMPERATIVELANG$>$ segment declares that this is a code segment written in
whatever IMPERATIVELANG may be, for example #JAVA for Java, #CPP for C++,
#PERL for Perl, #PYTHON for Python, etc.

  * •

#$<$INTENSIONALLANG$>$ segment declares that this is a code segment written in
whatever INTENSIONALLANG may be, for example #GIPL, #INDEXICALLUCID, #JLUCID,
#OBJECTIVELUCID, #TENSORLUCID, #ONYX111See [Gro04] for details on the Onyx
language., etc. as understood by the GIPSY.

###### Preprocessor Grammar

The initial grammar for the Preprocessor to be able to parse a GIPSY program
is shown in Figure 7. After having parsed a program, we have a Preprocessor
AST (PAST) that will be used further by the compilation process in the GIPC
and its submodules. The grammar and the framework were designed in such a way
so all the previous neat features of JLucid [MP05b]/Objective Lucid [MP05b]
still be present, such as embed() and are accessible to other dialects. In the
GICF, we generalize our function prototype declaration to be able to include
external code of any imperative language.

$\mathtt{<\\!\\!GIPSY\\!\\!>}$ | ::= |  $\mathtt{<\\!\\!DECLARATIONS\\!\\!>}$ $\mathtt{<\\!\\!CODESEGMENTS\\!\\!>}$
---|---|---
$\mathtt{<\\!\\!DECLARATIONS\\!\\!>}$ | ::= |  $\mathtt{<\\!\\!FUNCDECLS\\!\\!>}$ $\mathtt{<\\!\\!DECLARATIONS\\!\\!>}$
| $|$ |  $\mathtt{<\\!\\!TYPEDECLS\\!\\!>}$ $\mathtt{<\\!\\!DECLARATIONS\\!\\!>}$
| $|$ | $\epsilon$
$\mathtt{<\\!\\!FUNCDECLS\\!\\!>}$ | ::= |  #funcdecl $\mathtt{<\\!\\!PROTOTYPES\\!\\!>}$
$\mathtt{<\\!\\!TYPEDECLS\\!\\!>}$ | ::= |  #typedecl $\mathtt{<\\!\\!TYPES\\!\\!>}$
$\mathtt{<\\!\\!PROTOTYPES\\!\\!>}$ | ::= |  $\mathtt{<\\!\\!PROTOTYPE\\!\\!>}$ ; $\mathtt{<\\!\\!PROTOTYPES\\!\\!>}$
| $|$ | $\epsilon$
$\mathtt{<\\!\\!PROTOTYPE\\!\\!>}$ | ::= |  $\mathtt{<\\!\\!PSTART\\!\\!>}$ $\mathtt{<\\!\\!EMBED\\!\\!>}$
$\mathtt{<\\!\\!PSTART\\!\\!>}$ | ::= |  [ immutable ] $\mathtt{<\\!\\!TYPE\\!\\!>}$ [ [] ] $\mathtt{<\\!\\!ID\\!\\!>}$ ( $\mathtt{<\\!\\!TYPELIST\\!\\!>}$ )
$\mathtt{<\\!\\!EMBED\\!\\!>}$ | ::= | $\epsilon$
| $|$ |  : $\mathtt{<\\!\\!LANGID\\!\\!>}$ : $\mathtt{<\\!\\!URI\\!\\!>}$
| $|$ |  : $\mathtt{<\\!\\!LANGID\\!\\!>}$ : $\mathtt{<\\!\\!URI\\!\\!>}$ : $\mathtt{<\\!\\!ID\\!\\!>}$
$\mathtt{<\\!\\!TYPES\\!\\!>}$ | ::= |  $\mathtt{<\\!\\!TYPE\\!\\!>}$ ; $\mathtt{<\\!\\!TYPES\\!\\!>}$
| $|$ | $\epsilon$
$\mathtt{<\\!\\!TYPELIST\\!\\!>}$ | ::= |  $\mathtt{<\\!\\!TYPE\\!\\!>}$ [ [] ]
| $|$ |  $\mathtt{<\\!\\!TYPE\\!\\!>}$ [ [] ] , $\mathtt{<\\!\\!TYPELIST\\!\\!>}$
| $|$ | $\epsilon$
$\mathtt{<\\!\\!CODESEGMENT\\!\\!>}$ | ::= |  $\mathtt{<\\!\\!LANGDATA\\!\\!>}$ $\mathtt{<\\!\\!LANGID\\!\\!>}$
| $|$ |  $\mathtt{<\\!\\!LANGDATA\\!\\!>}$ $\mathtt{<\\!\\!EOF\\!\\!>}$
$\mathtt{<\\!\\!CODESEGMENTS\\!\\!>}$ | ::= |  $\mathtt{<\\!\\!CODESEGMENT\\!\\!>}$ $\mathtt{<\\!\\!CODESEGMENTS\\!\\!>}$
| $|$ | $\epsilon$
$\mathtt{<\\!\\!URI\\!\\!>}$ | ::= | $\mathtt{<\\!\\!CHARACTERLITERAL\\!\\!>}$
| $|$ | $\mathtt{<\\!\\!STRINGLITERAL\\!\\!>}$
$\mathtt{<\\!\\!ID\\!\\!>}$ | ::= |  $\mathtt{<\\!\\!LETTER\\!\\!>}$ ($\mathtt{<\\!\\!LETTER\\!\\!>}$ $|$ $\mathtt{<\\!\\!DIGIT\\!\\!>}$)*
$\mathtt{<\\!\\!LANGID\\!\\!>}$ | ::= |  #$\mathtt{<\\!\\!CAPLETTER\\!\\!>}$ ($\mathtt{<\\!\\!CAPLETTER\\!\\!>}$)*
$\mathtt{<\\!\\!TYPE\\!\\!>}$ | ::= | $\mathtt{<\\!\\!ID\\!\\!>}$
| $|$ | int
| $|$ | double
| $|$ | bool
| $|$ | float
| $|$ | char
| $|$ | string
| $|$ | void

Figure 7: Preprocessor Grammar for a GIPSY program.

The lexical elements, such as LETTER, LANGDATA, DIGIT, CAPLETTER, and
*LITERALs are not listed for brevity as they are merely standard and self-
explanatory lexical tokens except probably LANGDATA – this is character data
allowing any character sequence within except LANGID that serves as a
terminator of a code segment chunk.

Notice, the grammar is not bound to our current set of supported intensional
and imperative languages. Rather, the GIPC attempts to look up appropriate
compiler for each code segment automagically using LANGID for mapping at run-
time. The JavaCC version of the grammar can be found the
PreprocessorParser.jjt file.

The grammar has been amended from what was published in [MP05a] to include
LANGID in the EMBED production, the immutable keyword and arrays subscript
operator [] in the PSTART production. LANGID in EMBED is needed to be able to
pick the appropriate compiler for the included code as it may be written in
any imperative language. The immutable keyword is needed to allow a programmer
to assert that certain STs are immutable meaning given the same parameters
they always return the same result, and, therefore, their result can be safely
cached in the warehouse as such functions are declared side-effects free (e.g.
as the get42() method in Figure 9, page 9 can be marked as immutable). This
marking of methods will allow more efficient caching of the ST results of STs
known not to have side effects and has to be explicitly set by the programmer.
If the programmer by mistake marks a method with side effects as immutable,
then a program may exhibit erroneous execution at run-time by returning a
possibly incorrect value from the warehouse. There is no way to automatically
discover immutability of STs in GIPSY at this time (it may only be possible
when genuine imperative compilers are implemented). The array subscript
operator [] has been added to PSTART and TYPELIST productions to allow GIPSY
arrays (as a generalization of JLucid arrays) that are composed of the
elements of GIPSY types. The concrete imperative compilers implementing the
mapping (if possible) will have to do appropriate conversions from the native
arrays to GIPSY arrays.

#####  4.1.1.5 GIPSY Type System

While the main language of GIPSY, Lucid, is polymorphic and does not have
explicit types, co-existing with other languages necessitates definition of
GIPSY types and their mapping to a particular language being embedded. Figure
8 presents the design aspects of the GIPSY Type System.

Figure 8: GIPSY Type System.

Each class is prefixed with GIPSY to avoid possible confusion with similar
definitions in the java.lang package. The GIPSYVoid type always evaluates to
the Boolean true, as described earlier in Section 3.3.2. The other types wrap
around the corresponding Java object wrapper classes for the primitive types,
such as Integer, Float, etc. Every class keeps a lexeme (a lexical
representation) of the corresponding type in a GIPSY program and overrides
toString() to show the lexeme and the contained value. These types are
extensively used by the Preprocessor, imperative and intensional (for
constants) compilers, the SequentialThreadGenerator,
CommunicationProcedureGenerator, SemanticAnalyzer for the general type of
GIPSY program processing, and by the GEE Executor.

The other special types that have been created are either experimental or do
not correspond to a wrapper of a primitive type. GIPSYIdentifier type case
corresponds to a declaration of some sort of an identifier in a GIPSY program
to be put into the dictionary, be it a variable or a function name with the
reference to their definition. This is an experimental type and may be removed
in the future. Constants and conditionals may be anonymous and thereby not
have a corresponding identifier. GIPSYEmbed is another special transitional
type that encapsulates embedded code via the URL parameter and later is
exploded into multiple types corresponding to STs and their CPs. GIPSYFunction
and its descendant GIPSYOperator correspond to the function types for regular
operators and user defined functions. A GIPSYFunction can either encapsulate
an ordinary Lucid function (as in functional programming an which is
immutable) or an ST function (e.g. a Java method), which may easily be
volatile (i.e. with side effects). These four types are not directly exposed
to a GIPSY programmer and at this point are managed internally. The rest of
the type system is exposed to the GIPSY programmer in the preamble of a GIPSY
program, i.e., the #funcdecl and #typedecl segments, which result in the
embryo of the dictionary for linking, semantic analysis, and execution. Once
ST compilers return, the type data structures (return and parameter types)
declared in the preamble are matched against what was discovered by the
compilers and if the match is successful, the link is made.

#####  4.1.1.6 GICF Design

The GICF is the first generalization framework of hybrid programming in the
GIPSY. Implementation-wise, only Java is implemented as an imperative language
with an external compiler. However, provision was made for C/C++, Perl,
Fortran and Python with stub compilers. The class diagram describing GICF is
shown in Figure 9. On this diagram the interaction between a given imperative
compiler and the SequentialThreadGenerator and CommunicationProcedureGenerator
only shown for JavaCompiler to keep the clearer picture, but the same kind of
association will have to be maintained for all imperative compilers as the
IImperativeCompiler interface mandates. The EImperativeLanguages is a Java
interface enumerating all available imperative language compilers. It is used
by the GIPC to discover a given compiler for a language dynamically. As of
this writing, the enumeration is maintained by hand; however, it is planned to
be generated in the near future with a command-line-driven script or a RIPE
GUI automagically to facilitate addition of new languages.

Figure 9: GICF Design.

#####  4.1.1.7 Intensional Programming Languages Compiler Framework

As a consequence of GICF, a similar approach was applied to the intensional
compilers in the form of IPLCF. See the corresponding class diagram in Figure
10. The IIntensionalCompiler was designed and implemented by all the
intensional compilers we have. An enumeration EIntensionalLanguages of all
supported intensional languages was created, so the GIPC can pick needed
compiler at run-time as determined by the Preprocessor.

Figure 10: IPLCF Design. Figure 11: SIPL to GIPL Translator Integration.

Translation for all intensional compilers is done through the generic
Translator implemented by Aihua Wu in [Wu02]. The Translator has been
integrated into the GIPC.intensional.GenericTranslator package and split and
renamed as in Figure 11. Thus, every SIPL compiler refers to this translator
to acquire a GIPL AST at the end via generic implementation of
IntensionalCompiler.translate(). The Translator was refactored and augmented
to understand GIPSY Types (see Section 4.1.1.5) and ImperativeNode for
imperative languages. The TranslationParser and TranslationLexer collaborate
to compile intensional language translation rules (e.g. IndexicalLucid.rul)
files provided by each SIPL author.

#####  4.1.1.8 Sequential Thread and Communication Procedure Interfaces

This section details Sequential Thread and Communication Procedure interfaces.
The related class diagram is in Figure 12. The ICommunicationProcedure and
ISequentualThread are the core interfaces. Both extend Serializable in order
for us to be able to dump their concrete implementations to disk or
distributed storage using Java’s object serialization machinery. This is
needed for the GIPSYProgram container to be saved to disk or for an ST to be
able to reside in JavaSpaces [Mam05] implementation of the demand space
[VP05]. The ISequentialThread also extends Runnable to be true thread when
materialized, especially for the case of local execution. The Runnable
interface makes it possible for an implementing class to become a thread in
multithreaded environment in Java. The ICommunicationProceduresEnum is an
enumeration of all known to the GIPSY communication procedure types. The
NullCommunicationProcedure and RMICommunicationProcedure represent concrete
implementations for local threaded processing as well as RMI. Therefore, the
SequentialThreadGenerator is an abstract factory for all sequential threads
that has to be overridden by a language-specific sequential thread generator,
e.g. such as JavaSequentialThreadGenerator. Likewise,
CommunicationProcedureGenerator is a factory for CPs. The WorkResult class
represents the result of (computation) work done, which is also has to be
Serializable. Upon various communication needs the CommunicationStats is
returned by the ICommunicationProcedure API or the CommunicationException is
thrown indicating an error. The Worker class represents a collection of STs
and CPs being executed.

Figure 12: Sequential Thread and Communication Procedure Class Diagram.

#####  4.1.1.9 GIPC Design

In Figure 14 there is a hierarchy that all imperative and intensional
compilers should adhere to. The IImperativeCompiler interface is something
every imperative compiler implements to ease up the job of GIPC. A similar
interface has been invented for intensional languages – IIntensionalCompiler
for consistency.

A set of interfaces has been designed for all the present and future compilers
to implement. There are three interfaces so far:

  1. 1.

ICompiler is a superinterface for all compiler interfaces. It is implemented
by GIPC itself and by DFGAnalyzer, as shown in Figure 13.

  2. 2.

IIntensionalCompiler is a subinterface of ICompiler designated to
differentiate intensional compilers. It is implemented in part by the
IntensionalCompiler abstract class that most (for now all) intensional
compilers implement.

  3. 3.

IImperativeCompiler is a counterpart of IIntensionalCompiler. Its purpose is
similar to that of IIntensionalCompiler for imperative languages.

Figure 13: All GIPC Compilers.

The core difference between IIntensionalCompiler and IImperativeCompiler
versus the general ICompiler is that most (except for GIPL) of the intensional
compilers have to perform SIPL-to-GIPL translation; hence, the translate()
method, and all imperative compilers must produce communication procedures and
sequential threads as the result of their work; hence,
generateSequentialThreads() and generateCommunicationProcedures() methods are
provided. The abstract classes IntesionalCompiler and ImperativeCompiler
provide the most common possible implementation for all intensional and
imperative compilers respectively, so the underlying concrete compilers only
have to override some parts specific to the language they are to compile. If
extension of these classes is not possible for some reason (e.g. when writing
external GIPSY plugins when a compiler class already inherits from some other
class), they must implement their corresponding interface. Out of the concrete
classes on the diagram the author of this thesis fully implemented GIPC,
GIPLCompiler, IndexicalLucidCompiler, JLucidCompiler, ObjectiveLucidCompiler,
and JavaCompiler. The DFGAnalyzer of Yimin Ding was made to implement
ICompiler as it in fact compiles the “DFG code” out of GIPL or Indexical
Lucid.

Figure 14: Overall GIPC Design.

The overall design and integration of the GIPC participants is illustrated in
Figure 14. The GIPC class is the main compiler application that drives the
compilation process, so in the general case in invokes the Preprocessor,
intensional and imperative compilers required, the SemanticAnalyzer,
IdentifierContextCodeGenerator, Translator, and the GEERGenerator linker. It
also acts like a facade to other GIPSY modules. The major data structures,
such as AbstractSyntaxTree, Dictionary, CodeSegment, FormatTag,
ImperativeNode, and SimpleNode are created, accessed, or modified throughout
the modules during the compilation process. Out of imperative languages only
JavaCompiler is mentioned as it is the most advanced in this category. The
JLucidCompiler’s JLucidParser underneath invokes both JGIPLParser and
JIndexicalLucidParser as JLucid Section 3.1 provides extensions to both of
these languages. A number of association links have been removed from the
diagram to maintain clarity as these links are intuitive or present in detail
diagrams.

#####  4.1.1.10 GIPC Class as a Meta Processor

The GIPC (a concrete class) acts here as so-called “meta processor” that
drives the entire compilation process and invokes appropriate submodules in
order to come up with a compiled version of a GIPSY program. This involves
calling the Preprocessor, then feeding its output to whatever concrete
compilers for the code segments of the GIPSY program, collecting the output of
them (various ASTs, dictionaries), performing semantic analysis, and linking
all the parts back together in a binary form. This portable binary version of
the GIPSY program is to either be serialized as an executable file for later
execution by the GEE or optionally to be fed directly to the GEE.

#####  4.1.1.11 Calling Sequence

The sequence diagram in Figure 15 illustrates the entire compilation process
and the data structures passed between the modules. This is the roundtrip
description of the implementation efforts. The two followup diagrams detail
the differences in the compilation process between the imperative and
intensional languages. The general compilation process begins by reading the
source GIPSY program and converting it into a meta token stream of types,
declarations, and code segments by the Preprocessor. The Preprocessor takes
that input and with its own parser produces a preprocessor AST and an embryo
of a dictionary with the identifiers and types declared in the imperative code
segments for further semantic linking. The latter is used to produce
imperative stubs for cross-segment type checks. The former contains primarily
code segments written in various languages. The GIPC takes these code segments
and creates appropriate compiler threads, one for each code segment. Then,
each compiler tries to compile its own chunk and produces a portion of a main
AST. Since we treat the IPL part as a main program, its AST is considered to
be the main skeleton tree. The ASTs produced by the imperative compilers
(which really contain a single ImperativeNode) are secondary and should be
merged into the main when appropriate. Once all the compiler threads are
successfully done, the GIPC collects all the ASTs and performs linking via the
GEERGenerator. The combined AST is now a subject to the semantic analysis and
the function elimination. Once semantic analysis is complete, the final post-
linking is performed where all the pieces of the GIPSYProgram are combined
together and its instance is serialized to disk. Optionally, right after
compilation the GEE may be invoked to start the execution of the just compiled
program.

Figure 15: Sequence Diagram of GIPSY Program Compilation Process.

There is no any preference made in GIPC on the number and the order of
intensional and imperative compilers executed. This may result in several main
intensional programs (if the source code contained more than one intensional
code segment) or unused imperative nodes (an imperative segment is declared
but the code from it is unused). For the former we maintain an array of ASTs
in the GIPSYProgram, so that when the actual program is executed, the same
number of the GEE Executor threads are started and all main ASTs are evaluated
in parallel providing the result set of a computation instead of a single
result. Detailed sequence diagrams of the intensional and imperative
compilation processes are in Figure 16 and Figure 17 to illustrate the
differences in compiling intensional and imperative code segments.

Figure 16: Sequence Diagram of Intensional Compilation Process. Figure 17:
Sequence Diagram of Imperative Compilation Process.

#####  4.1.1.12 Compiling and Linking

###### Multiple Intensional Parts

In a GIPSY program we may possibly have multiple intensional parts. For
example, if a GIPSY programmer gave a GIPL expression, an Indexical Lucid
expression and a couple of Java procedures in the same source GIPSY program,
what is the meaning of that setup would be? In this case, we can say that we
evaluate two independent intensional expressions in parallel that happened to
share the same imperative part. Thus, for such a GIPSY program there will be
two instances of GEE running. The GEE is to extended to accept a forest of
ASTs to be processed in parallel.

###### Imperative Stubs

When the Preprocessor completes its job, it has to create some stubs in the
intensional parts of the program for the symbols declared outside of those
parts (e.g. Java functions) so that the appropriate intensional compiler does
not complain about undefined symbols when producing the AST because the
intensional compilers are not aware of anything outside their work scope.
Later on, the corresponding stub nodes in the AST are found and replaced with
the real contents at the linking stage.

###### NCP Generator as a Type Processor

The NCP generator will act very much like a type processor and will have to
look inside the imperative code segments analyzed/compiled by the ST
generator. This kind of type processing is needed to decide on communication
procedures (CPs) to be generated for that ST. It issues warnings if the
compiled version of the data structures to be sent is not portable. The role
of the NCP generators in the GIPSY implementation is played by the imperative
compilers, such as JavaCompiler.

###### GEER Generator as a Linker

The GEER Generator (see GEERGenerator in Figure 19) in the backend acts like a
linker of all parts of a GIPSY program. It gathers all the resources from the
compiler set, such as ASTs, ICs, CPs, STs, and the dictionary. Then, it
replaces the stubs in the intensional part with the nodes from the imperative
ASTs (STs accompanied with their respective CPs) forming a complete composite
AST ready for consumption by the GEE. All this will be serialized as a
GIPSYProgram class instance. The GEERGenerator is invoked two times – first
prior SemanticAnalyzer to assemble a complete AST, and then after semantic
analysis and function elimination to set up the finalized dictionary and
program name.

#####  4.1.1.13 Semantic Analyzer

Figure 18: Semantic Analyzer.

The semantic analyzer detailed design diagram is shown in Figure 18.
Originally implemented by Aihua Wu, the class was renamed from Semantic [Wu02]
to a more complete name of SemanticAnalyzer and placed under the GIPC package.
Relevant changes include integration of storage.Dictionary (previously was
java.util.Vector), storage.DictionaryItem (formerly Item_in_Dict [Wu02]),
storage.FunctionItem (formerly Fun_Item [Wu02], serves for function
description). The SemanticAnalyzer had to be taught to recognize new GIPSY
types (see Section 4.1.1.5) with base GIPSYType class for object, embed, and
array processing, ImperativeNode for sequential threads and communication
procedures, and a general AbstractSyntaxTree.

#####  4.1.1.14 Interfacing GIPC and GEE and Compiled GIPSY Program

Now, let us formally define the notion of a stored compiled GIPSY program, as
a GEER or the interface between the two major modules - GIPC and GEE. Until
this point, the GEE accepted from GIPC as the input AST of an intensional part
and a dictionary of symbols. This suggests having serialized the AST and the
dictionary. With the invent of JLucid, communication procedures (CPs) and
sequential threads (STs) became relevant and should belong to the GIPC-GEE
interface. Thus, a compiled GIPSY program may have several of CPs and STs
serialized along. While STs and CPs are present within imperative AST nodes,
references to them are recorded here for quicker access and decision making by
the GEE. Then, as GEE produces demands (especially over RMI or Jini, [VP05])
for each intensional identifier in the dictionary an Identifier Context (IC)
class created [LGP03, Lu04]. This is needed because every such identifier
represents a Lucid expression to be evaluated by the engine, and as such
should also be part of the compiled GIPSY program. The corresponding class
diagram is in Figure 19. It includes the GIPSYProgram and all its associations
with GIPC, GEE, GEERGenerator, and the storage classes.

Figure 19: Class diagram describing GIPSYProgram.

To summarize, the GIPC-GEE interface is the GIPSYProgram representing
encapsulation of the five parts:

  1. 1.

Linked AST(s)

  2. 2.

Dictionary

  3. 3.

A set of STs

  4. 4.

A set of CPs

  5. 5.

A set of ICs.

On the diagram in Figure 4 GIPSYProgram defines and corresponds to the GEER.

####  4.1.2 JLucid

#####  4.1.2.1 Design

Figure 20: JLucid Design.

The class diagram describing JLucid is shown in Figure 20. The implementation
of JLucid parser-wise is heavily dependent on that of Indexical Lucid as the
largest chunk of the IPL work is the same. JLucid adds a preprocessor
JLucidPreprocessor class that is responsible for parsing initial source JLucid
program and extract Java and Lucid parts. The JLucidParser class is the one
that manipulates javacc-generated parsers amended to support embed() and
arrays. The sequence diagram describing the details of the compilation
sequence of JLucid is presented in Figure 21.

Figure 21: JLucid Compilation Sequence.

JLucid implements generation of Java sequential threads (STs) and their
communication procedures (CPs); thus, necessitating
JavaSequentialThreadGenerator and JavaCommunicationGenerator. For uniformity,
portability, and testing reasons, we also decided to send the source code
over, that can possibly be compiled on the remote machine. All this is done by
the GICF-integrated JavaCompiler, see Section 4.1.2.3.

#####  4.1.2.2 Grammar Generation

As it was shown in Chapter 3, the JLucid syntax extension to GIPL and
Indexical Lucid is minimal. The JavaCC grammars we use, are stored in the .jjt
files for the original two dialects. If we decide to have very similar grammar
files for JLucid to support JLucid extensions (arrays and embed()), then if
the original grammar has a bug, the fix will have to be propagated to all the
derived grammars, which will not scale from the maintenance point of view as
there will be similar small modifications from Objective Lucid and other
dialects. Thus, it was decided to only maintain the original grammars of GIPL
and Indexical Lucid and generate the ones for the dialects with the minimal
changes, so that each dialect only maintains the part that is relevant to its
syntactic extension.

For JLucid three bash shell scripts were created to process the original
JavaCC grammars of GIPL and Indexical Lucid and generate appropriate extended
versions for JLucid. These include jlucid.sh that generates JavaCC productions
for arrays and embed(), JGIPL.sh that alters the original GIPL.jjt grammar to
suit the needs of JLucid mostly in terms of class and package names and the
new productions. Similarly, the JIndexicalLucid.sh script exists for
processing of the IndexicalLucid.jjt file. The scripts are rather small and
presented in the Appendix D.

#####  4.1.2.3 Free Java Functions and Java Compiler

As defined in Chapter 3, by “free Java functions” we mean is that the
corresponding Java STs don’t have an enclosing Java class as far as JLucid
source code concerned. However, the enclosing class must exist when compiling
a Java program according to Java’s syntax and semantics. Thus, implementation-
wise we generate such a class internally that wraps all our sequential
threads, as e.g. in Section 4.1.1.8, and we compile that class. This job of
wrapping is delegated to the JavaCompiler, a member of the imperative
compilers framework (see Section 4.1.1.1). The JLucidCompiler as shown in
Figure 21 at some point invokes the JavaCompiler, and what the JavaCompiler
does internally is illustrated in Figure 22.

Figure 22: Java Compilation Sequence.

Being an imperative compiler, the JavaCompiler is obliged to produce the Java
STs and CPs among other things. The core of this process is the wrap() method
where the actual “wrapping” our pseudo-free Java functions into an internal
class occurs. The generated source code .java file is saved and is fed to the
external javac compiler as of this implementation. If there was no compilation
errors, a corresponding .class or series of .class files (for the case of
nested classes) is generated. The generated classes are reloaded back by the
JavaCompiler and their members that are of interest to us retrieved via the
Java Reflection Framework [Gre05], thus we obtain an array of references to
the ST methods and their parameters and assign them to our own data
structures. After this process completes, the corresponding FormatTag
describing the Java language and the compiler is created and all information
is embedded into the ImperativeNode, which represents a single and the only
node in the imperative AbstractSyntaxTree. Later on, this imperative node or
its pieces will replace a corresponding stub in the main intensional AST.

#####  4.1.2.4 Arrays

Implementation of arrays in JLucid coincides closely with the implementation
of objects in Objective Lucid in Section 4.1.3. As a part of the GIPSY Type
System (see Section 4.1.1.5), we employ the GIPSYArray (see Figure 8) type to
hold the array base type and its members and an overall value. As proposed
further, we treat arrays internally as objects (and objects as arrays), so
GIPSYArray is an extension of GIPSYObject that has a base type asserting the
data type of the all the elements in the arrays (as our arrays a homogenous
collection of elements). Thus, when a syntactic array token is parsed, a
corresponding instance of GIPSYArray is created to hold the type and value
information for later processing. The SemanticAnalyzer and the Executor are
made to understand the array type and apply similar type checking or execution
rules to a collection of values instead of a single value.

It might look like this approach will clash with the use of arrays in Java,
i.e., when a developer wishes to use Java arrays (or if a library already
implements some functionality via Java arrays). This should not be a problem
(though will require a more thorough investigation in the future work), when
we perform type matching by the base element type, as described in Section
4.1.1.4. The JavaCompiler is responsible for the appropriate conversion of the
native-to-GIPSY type conversions, by supplying a TypeMap such that it can also
be used by the GEE at run-time. Similar comments can be said of the native
array types that might exist in other imperative languages that we would be
hoping to support.

#####  4.1.2.5 Implementing embed()

To implement embed() we define a type GIPSYEmbed to fetch the file pointed by
the URL and hold it in there. In JLucid, a .java or .class file (later also a
.jar file) is loaded from either local or remote location pointed by the URL
as follows: if it is a .java file, it’s fetched and compiled similarly to the
generated class, but the name is static and known; with the .class file we
skip the compilation process, but extraction of the sequential threads is the
same; for the .jar its examined with the JarInputStream and JarEntry Java
classes to extract the class information.

#####  4.1.2.6 Abstract Syntax Tree and the Dictionary

When running the JLucid compiler in stand-alone mode, all the preprocessing
and re-assembling the intensional and imperative pieces into the combined main
AST happens in here, not in the GIPC, so the JLucid compiler returns a
complete linked AST with all imperative nodes linked in place and a proper
dictionary of identifiers, both intensional and imperative. JLucid compiler,
however, reused the Preprocessor and other parts of the new framework
internally instead of re-inventing the wheel.

The JLucidPreprocessor uses the general Preprocessor class to do the job of
chunkanizing the code segments and preparing initial imperative stubs. This
necessitated adding the #funcdecl segment in the JLucid programs that
previously did not have one in Chapter 3, to simplify preprocessing and
generation of the dictionary. The JLucidPreprocessor is set to reject any
other code segments than #JAVA, #JLUCID, or #funcdecl.

If the JLucidCompiler invoked from the GIPC as a part of general compilation
process (see Figure 15), the #JAVA segment will no longer be really processed
internally, and instead, GIPC will call JavaCompiler externally to the
JLucidCompiler, so essentially the JLucidCompiler will be responsible only for
the Lucid part (with arrays and embed()).

####  4.1.3 Objective Lucid

This section addresses problems that arise when implementing Objective Lucid.
These include internal implementation to support the dot-notation, extension
to semantic analysis to be able to manipulate object data types (very likely
user-defined), and making it all work in the GICF and General Eduction Engine
(GEE) of the GIPSY by correctly forming the abstract syntax tree (AST) that
includes object data types.

#####  4.1.3.1 Design

Figure 23: Objective Lucid Design. Figure 24: Objective Lucid Compilation
Sequence.

The class diagram describing Objective Lucid is in Figure 23. Since the JLucid
compiler already does most of the legwork, Objective Lucid simply extends it
to add the dot-notation and some extra post-processing when unrolling the
objects. The corresponding compilation sequence is shown in Figure 24.

#####  4.1.3.2 Grammar Generation

Like with JLucid, the grammar files are generated for Objective Lucid using
bash shell scripts, ObjectiveGIPL.sh and ObjectiveIndexicalLucid.sh. These
scripts work with the grammars produced by the JLucid scripts (see Section
4.1.2.2) by simply extending them with the dot-notation production and fixing
up names of classes and packages. These scripts are presented in the Appendix
D.

#####  4.1.3.3 Object Instantiation

Normally, when a Lucid program refers to a Java object, it has to instantiate
it first by either calling a pseudo-free Java function that returns an object
instance or to call the constructor directly. This instantiation has to be
explicit at the beginning of the program to avoid Java’s NullPointerException
at run-time. Internally, the object instance is created using Java Reflection
[Gre05] by first loading and then initializing the needed class with
Class.forName("ClassXB").newInstance(). Referencing static members do not
require a class instance, and can be accessed using the class name, in this
case we just keep the Class.forName("ClassXB"). We also keep the needed
references to the object itself and its members in the GIPSYObject type of the
GIPSY Type System.

#####  4.1.3.4 The Dot-Notation

Implementing the dot-notation extension of JLucid is the easiest task of the
three. In fact, the E.id productions are just a syntactic sugar that can be
wrapped around already existing mechanisms of JLucid to include Java functions
as mentioned in Section 3.2.1.1. The compiler simply generates a set of
pseudo-free Java functions for every object member referenced from the
intensional program. These will be easy to place into the AST just the way
JLucid does it. In other words, this is achieved by automatic generation of
implicit accessor Java functions that had to be explicit in JLucid.

#####  4.1.3.5 Abstract Syntax Tree and the Dictionary

The GIPC (General Intensional Programming Compiler) generates abstract syntax
trees (AST) of all compiled GIPSY program parts, and constructs the GEER
(General Eduction Engine Resources), which is a data dictionary storing all
program identifiers, encapsulated with all ASTs generated at compile time.
Simply put, the GEER encapsulates all the meaning of a GIPSY program, and all
necessary resources to enable the GEE to execute the programs correctly. The
AST and the dictionary contain the generated accessor identifiers that are
processed by the JLucid mechanisms, as described previously. This is possible
because Java’s built-in class Class can provide us with all the meta-
information about its members through enumeration that we can place in the AST
and the dictionary. Little changes from the way JLucid processes that except
that the object members are put into the dictionary and acted upon as an array
of homogeneous types as described in the follow up section.

The ObjectiveLucidPreprocessor also makes use of the general Preprocessor, but
unlike JLucidPreprocessor, it also accepts the #typedecl segment as with
objects come user-defined types, so these have to be listed if used by the
Lucid part.

#####  4.1.3.6 Objects as Arrays and Arrays as Objects

Implementation-wise, we propose to treat arrays of JLucid as a special case of
objects and, the other way around, the objects be a generalization of arrays.
An array can be broken into its elements where every element is evaluated as
an expression under the same context. Thus, evaluating:

A[4] @ [d:4] where dimension d; A[#.d] = 42 * #.d fby.d (#.d - 1); end;

is equivalent to evaluating four Indexical Lucid expressions (possibly in
parallel). Under this point of view objects can be viewed as arrays where
every atomic member is evaluated as if it were an array element. Basically, we
denormalize an object into primitives and evaluate them. If an object
encapsulates other objects, then these are in turn denormalized and put into
the definition environment (dictionary). In other words, if you have an array
of four elements a[4], the elements are evaluated as four independent
expressions. Likewise, an object that has four data members, each of them is
evaluated as an expression under the same context.

Essentially, an array is a collection of atomic elements of the same type.
When evaluating say an array of four elements a[4] at some context [d:4], we
are, in fact, evaluating four ordinary Lucid expressions (possibly in
parallel) in the same context. Likewise, an object is a collection of atomic
elements of (possibly) different types. In case an object encapsulates another
object, that other object can in turn be split into atoms, and so on. All
atoms of an object evaluate as independent Lucid expressions, just like array
elements.

Thus, from Objective Lucid’s point of view, the following are equivalent:

(a) int a[4];

(b) class foo { int a1; int a2; int a3; int a4; }

So, internally, we represent (a) in the definition environment as:

a_4 // scope identifier a_4.a1 a_4.a2 a_4.a3 a_4.a4

Under the scope of array a_4 (a generated id) there are four members, and
a_4.a* comprise a denormalized identifier, also generated. And (b) will
become:

foo // scope identifier foo.a1 foo.a2 foo.a3 foo.a4

where foo.a* are generated variable identifiers in the definition environment.
Encapsulation will be handled in the following way:

class bar { int b1; int b2;
foo oFoo = new foo(); } bar bar.b1 bar.b2 bar.foo bar.foo.a1 bar.foo.a2
bar.foo.a3 bar.foo.a4

To paraphrase and explain in another example, if we have three separate Lucid
expressions:

// float a @ [d:2] where dimension d; a = 2.5 fby.d (a + 1); end; // integer b
@ [d:2] where dimension d; b = 1 fby.d (b + 1); end; // ASCII Char c @ [d:2]
where dimension d; c = ’a’ fby.d (c + 1); end;

Now if we group a, b, and c as a class:

class foo { float a = 2.5; int b = 1; char c = ’a’; public foo() {} }

So when we write:

f @ [d:2] where dimension d; f = foo() fby.d (f + 1); end;

we mean there start three subexpression evaluations:

f.a @ [d:2] where dimension d; f.a = foo().a fby.d (f.a + 1); end; f.b @ [d:2]
where dimension d; f.b = foo().b fby.d (f.b + 1); end; f.c @ [d:2] where
dimension d; f.c = foo().c fby.d (f.c + 1); end;

We say these are equivalent where the f in all expressions refers to the same
object’s instance (i.e. there are not three objects constructed, only one).
Similarly (nearly identically) we implement arrays:

a[3] @ [d:2] where dimension d; a = [1, 2, 3] fby.d (a + 1); end;

The above means:

array a { int a1 = 1; int a2 = 2; int a3 = 3; int length = 3; }

a1 @ [d:2]
where dimension d; a1 = 1 fby.d (a1 + 1); end; a2 @ [d:2]
where dimension d; a2 = 1 fby.d (a2 + 1); end; a3 @ [d:2]
where dimension d; a3 = 1 fby.d (a3 + 1); end;

The three subexpressions run in parallel, but refer back to the same array.
Should there be a need in one of the three subexpressions to use an array
value produced by another subexpression, they generate a demand for that
value.

###  4.2 External Design

The external design encompasses user interface design as well as external
software interfaces. In this work, a web interface to the GIPSY as well as
command-line interfaces are presented as a part of UI followed by the API of
the two external libraries used, JavaCC and MARF.

####  4.2.1 User Interface

#####  4.2.1.1 WebEditor – A Web Front-End to the GIPSY

The user interface designed for the GIPSY in the scope of this thesis includes
a Servlet-driven web interface to the GIPSY daemon server running on our
development server for trying out GIPSY programs online. The web interface in
a form of a web page allows a connected user to enter, compile, run, and trace
GIPSY programs. Users are able to submit their own GIPSY programs (in any
supported Lucid dialect) or choose and modify from existing programs from the
GIPSY CVS repository (see [RG05a]) and then launch the computation. The GIPSY
servlet front-end generates demands through RIPE and returns back results
along with an execution trace to a web form. A screenshot of this interface is
illustrated in Figure 25.

Figure 25: GIPSY WebEditor Interface.

#####  4.2.1.2 GIPSY Command-Line Interface

Synopsis:

        gipsy [ OPTIONS ]
        gipsy --help | -h

This is an all-entry point for all of GIPSY that bundles all the modules. It
generally passes all the options to RIPE for further dispatching. When the
server part (see Section 7.10) is complete, this will be a GIPSY daemon
server. The command line interface includes the following options:

  * •

\--help or -h displays application’s usage information.

  * •

\--compile-only tells to compile a GIPSY program only and return the result of
the compilation (error or success messages) and the compiled program itself.
This will not invoke the GEE for execution after compilation. The option is
primarily for quick tests in development setups.

  * •

\--debug tells to run in the debug/verbose mode.

It is possible to run the GIPSY by either invoking the GIPSY.class directly,
by running a corresponding gipsy.jar (see Appendix C.2) file, or using a
provided wrapper script gipsy. The latter is the simplest one to use as it
includes all the necessary options for the JVM and searches for the executable
.jar in several common places. A good idea is to put gipsy somewhere under
one’s PATH. (A similar approach applies to the other tools mentioned in the
follow up sections, such as ripe, gipc, gee, and regression. The tools exist
for both Unix and Windows in the form of shell scripts and batch files.)

Example uses of the GIPSY application include:

  * •

gipsy or gipsy --help

  * •

gipsy --compile-only

  * •

gipsy --compile-only --debug

Where \--debug can be combined with any of these, otherwise the options are
exclusive.

#####  4.2.1.3 RIPE Command-Line Interface

Synopsis:

        ripe [ OPTIONS ]
        ripe --help | -h

The RIPE command-line interface right now acts mostly to activate various own
submodules (e.g. textual or DFG editors) or dispatch requests from users to
the other main modules, such as GIPC and GEE. The command-line interface
includes the following options:

  * •

\--help or -h displays application’s usage information.

  * •

\--gipc=‘$<$GIPC OPTIONS$>$’ tells RIPE to invoke GIPC with a set of GIPC
options (see Section 4.2.1.4).

  * •

\--gee=‘$<$GEE OPTIONS$>$’ tells RIPE to invoke GEE with a set of GEE options
(see Section 4.2.1.5).

  * •

\--regression=‘$<$REGRESSION OPTIONS$>$’ tells RIPE to invoke Regression
testing with a set of its options (see Section 4.2.1.6).

  * •

\--dfg=‘$<$DFG EDITOR OPTIONS$>$’ tells RIPE to start the DFG editor with its
options. Currently, the DFGEditor Java class is a stub, and instead, the DFG
Editor of Yimin Ding [Din04] is started via a separate program, lefty. It is
planned the DFGEditor class would be a wrapper for the program in the future.
Therefore, all DFG editor options are ignored for now, but a provision is made
for the future.

  * •

\--txt=‘$<$TEXTUAL EDITOR OPTIONS$>$’ tells RIPE to start the textual editor
with its options. Note, at the time of this writing TextualEditor is just a
stub, and as such does not have any options, but a provision is made when it
does.

  * •

\--debug tells to run in the debug/verbose mode.

Example uses of the RIPE application include:

  * •

ripe or ripe --help

  * •

ripe --compile-only

  * •

ripe --compile-only --debug

#####  4.2.1.4 GIPC Command-Line Interface

Synopsis:

        gipc [ OPTIONS ] [ FILENAME1.ipl [ FILENAME2.ipl ] ... ]
        gipc --help | -h

The command line interface for GIPC inherited some options from Lucid [Ren02]
and includes the following options:

  * •

\--help or -h displays application’s usage information.

  * •

[FILENAME1.ipl [FILENAME2.ipl] ...] tells GIPC to compile a GIPSY program as
indicated by the FILENAME. It is possible to have more the one input file for
compilation. If this is the case, the same number of instances of GIPC threads
will be initially spawned to compile those programs. Notice, however, this
does not mean all the files (in case of multiple .ipl files) comprise one
program and then linked together afterwards as in typical C or C++ compilers.
Instead, each .ipl file is treated as a stand-alone independent GIPSY program.

  * •

\--stdin tells GIPC to interpret the standard input as a source GIPSY program.
This is the default if no FILENAME is supplied.

  * •

\--gipl or -G (came from Lucid [Ren02] for backwards compatibility) tells GIPC
to interpret the source program unconditionally as a GIPL program (by default
no assumption is made and GIPC attempts to treat the incoming source code as a
general GIPSY program). It is primarily used to quickly test the GIPL compiler
only, without extra overhead or preprocessing. It is also used by the
Regression application for that same reason.

  * •

\--indexical or -S (came from Lucid [Ren02]) tells GIPC to interpret the
source program unconditionally as an Indexical Lucid program.

  * •

\--jlucid tells GIPC to interpret the source program unconditionally as a
JLucid program.

  * •

\--objective tells GIPC to interpret the source program unconditionally as an
Objective Lucid program.

  * •

\--translate or -T (came from Lucid [Ren02]) enables SIPL-to-GIPL translation.
This option is implied by default (as opposed to be optional in Lucid). It
tells the GIPC to interpret the input program unconditionally as a non-GIPL
program that requires operator and function translation. The option has no
effect with \--gipl as GIPL is the only intensional language that does not
require any further translation.

  * •

\--disable-translate turns off automatic translation (in case the user knows
that an incoming non-GIPL program has nothing to translate, which is rarely
the case; otherwise, the GIPC will bail out with an error).

  * •

\--warnings-as-errors tells to treat compilation warnings as errors and stop
compilation after displaying them.

  * •

\--gee tells GIPC to run the compiled program immediately after compilation
(if successful) by feeding it directly to the GEE. The default is that the
compiled GIPSY program is saved into a file where the original name is
suffixed with the .gipsy extension.

  * •

\--dfg tells GIPC to perform DFG code generation as a part of the compilation
process.

  * •

\--debug to run in a debug/verbose mode.

Example uses of the GIPC application include:

  * •

gipc or gipc --help or gipc -h

  * •

gipc life.ipl

  * •

gipc --disable-translate --gee --debug life.ipl

  * •

gipc --gipl --debug gipl.ipl

  * •

gipc --jlucid --stdin

#####  4.2.1.5 GEE Command-Line Interface

Synopsis:

        gee [ OPTIONS ] [ FILENAME1.gipsy [ FILENAME2.gipsy ] ... ]
        gee --help | -h

The command line interface includes the following options:

  * •

\--help or -h displays application’s usage information.

  * •

[FILENAME1.gipsy [FILENAME2.gipsy] ...] tells GEE to run a stored version of a
compiled GIPSY program as indicated by the FILENAME. It is possible to have
more than one input file for execution. If this is the case, the same number
of instances of GEE threads will be initially spawned to run those programs.
The programs will run concurrently, but there should not be any interference
or communication in their execution except they may share the output resource.

  * •

\--stdin tells GEE to interpret the standard input as a compiled GIPSY
program. This is the default if no FILENAME is supplied.

  * •

\--all tells GEE to start all implemented services/servers locally (threaded,
RMI, Jini, DCOM+, and CORBA).

  * •

\--threaded tells GEE to start the threaded server only.

  * •

\--rmi tells GEE to start the RMI service.

  * •

\--jini tells GEE to start the Jini service.

  * •

\--dcom tells GEE to start the DCOM+ service.

  * •

\--corba tells GEE to start the CORBA service.

  * •

\--debug tells GEE to run in the debug/verbose mode.

Example uses of the GEE application include:

  * •

gee or gee --help or gee -h

  * •

gee life.gipsy

  * •

gee --disable-translate --threaded --debug life.gipsy

  * •

gee --all --debug gipl.gipsy

  * •

gipc --rmi --jini indexical.gipsy

#####  4.2.1.6 Regression Testing Application Command-Line Interface

Synopsis:

        regression [ OPTIONS ]
        regression --help | -h

The Regression application and its test suite are presented in detail in
Section 5.1. The application, based on options, invokes either GIPC or GEE or
both directly feeding a pre-selected list of test source programs. The command
line interface includes the following options:

  * •

\--help or -h displays application’s usage information.

  * •

\--sequential tells to run sequential tests (default).

  * •

\--parallel tells to run parallel tests.

  * •

\--gipl tells to test pure GIPL programs only.

  * •

\--indexical tells to test pure GIPL and Indexical programs with the Indexical
Lucid compiler.

  * •

\--gipsy tells to test general-style GIPSY programs with code segments.

  * •

\--gee if specified, tells to run the GEE after compilation (default).

  * •

\--all tells to do all of the above tests in one run (default).

  * •

\--directory tells to pick source test files from a specified directory
instead of pre-set directories from the GIPSY source tree

  * •

\--debug tells to run in the debug/verbose mode.

Example uses of the Regression application include:

  * •

regression or regression --help or regression -h

  * •

regression --gipl

  * •

regression --parallel --indexical

  * •

regression --all --debug

  * •

regression --directory=/some/gipsy/misc/tests --all --debug

####  4.2.2 External Software Interfaces

#####  4.2.2.1 JavaCC API

JavaCC-generated code contains a number of common classes and interfaces,
regardless of the language a parser is generated for. These have to do with
AST nodes, tokens, token types, character streams, and alike. The most often
used class out of this bundle is SimpleNode, which is a concrete node in the
AST. These classes have to be periodically refreshed by compiling the source
grammar when a newer version of javacc comes out.

Figure 26: JavaCC- and JJTree-generated Modules Used by Several GIPC Modules.

The below are JavaCC API/modules [VC05] used by the GIPSY and their
description. The corresponding class diagram is in Figure 26.

  * •

Node is the common interface for all occurrences of SimpleNode to implement
(see below).

  * •

The SimpleNode class represents a concrete node in every AST in the GIPC. Once
generated, this class is usually customized according to the needs of the
given parser/compiler. All concrete instances, however, implement the same
Node interface above. At the time of this writing, there are three SimpleNode
occurrences in the GIPSY source tree: the common one in gipsy.GIPC.intensional
for all the SIPLs and GIPL, as per original implementation presented in
[Ren02]. It is a basis for a GIPL AST aside from the related parsers known to
the SemanticAnalyzer and GEE’s Executor. This implementation is wrapped-around
by AbstractSyntaxTree that the rest of the modules know. Then, a customized
subclass of it is in gipsy.GIPC.DFG.DFGAnalyzer of Yimin Ding [Din04]. It was
made a subclass because a large portion of the code is identical. Finally, the
last one is in gipsy.GIPC.Preprocessing used by the Preprocessor. This
occurrence of SimpleNode was kept as-is due to the significant differences and
purpose with the former two.

  * •

The ImperativeNode is another implementation of the Node interface created
manually for all the imperative language compilers. The ImperativeNode
represents an AST of a single node encapsulating STs, CPs, some meta
information that came from a given imperative compiler. The reason for this is
to maintain a global AST for a GIPSY program where all nodes implement the
same interface.

  * •

SimpleCharStream is a common javacc utility that treats incoming source code
stream as a set of ASCII characters without extra UNICODE processing.

  * •

ParseException is a common generated type of exception to indicate a parse
error. It was made manually to subclass GIPCException from the GIPSY
Exceptions Framework (see Section 4.2.3.2) for uniform exception handling.

  * •

TokenMgrError a subclass of java.lang.Error primarily to signal lexical errors
in the incoming source code or token processing in general by a given parser
(e.g. by invoking a static parser twice).

#####  4.2.2.2 MARF Library API

Figure 27: MARF Utility Classes used by the GIPSY. Figure 28: Dictionary and
DictionaryItem API Figure 29: Dictionary Usage within the GIPSY

MARF (see Section 2.6.3) has a variety of useful utility and storage-related
modules that conveniently found their place in GIPSY. Most of these come from
the marf.util package as well as marf.Storage.222Later some natural language
processing (NLP) modules in marf.nlp of MARF might also get used in the GIPSY
as a part of another research project. The below are MARF API/modules used by
GIPSY and their description:

  * •

marf.util.FreeVector is an extension of java.util.Vector that allows
theoretically vectors of infinite length, so it is possible to set or get an
element of the vector beyond its current physical bounds. Getting an element
beyond the boundaries returns null, as if the object at that index was never
set. Setting an element beyond bounds automatically grows the vector to that
element. In the GIPSY, marf.util.FreeVector is used as a base for our
Dictionary as shown in Figure 28. Figure 29 shows all the modules that are now
using Dictionary instead of java.util.Vector. The corresponding class diagram
of the MARF’s util API is shown in Figure 27.

  * •

marf.util.OptionProcessor module is extensively used by the command-line user
interfaces (see Section 4.2.1) of GIPSY, GIPC, GEE, and Regression. A
convenient way of managing command-line options in a hash table and validating
them.

  * •

marf.util.BaseThread class encapsulates some useful functionality used in
threaded versions of GEE and GIPC, which Java’s java.lang.Thread does not
provide:

    * –

maintaining unique thread ID (TID) among multiple threads and reporting it
(for tracing, debugging, and RIPE). A note is added here that Java 1.5.* now
also provides a notion of a TID, but marf.util.BaseThread was written prior to
that and GIPSY remains Java 1.4-compliant still. Plus, MARF’s way of handling
this is more flexible.

    * –

adapted human-readable trace information via toString()

    * –

access to the Runnable target that was specified upon creation.

    * –

integration with marf.util.ExpandedThreadGroup, see below.

  * •

marf.util.ExpandedThreadGroup allows to start, stop, or other group operations
that Java’s java.lang.ThreadGroup doesn’t provide. ExpandedThreadGroup is, for
example, used in GIPC to create a group of compiler threads (in GIPSY every
compiler is a thread), one for each language chunk, that will run
concurrently. Additionally, a group of GEE, or rather, Executor threads would
run in the case of a forest of ASTs.

  * •

marf.util.Arrays groups more array-related functionality together than the
java.util.Arrays class does, for example copying (homo- and heterogeneous
types) and converting to java.util.Vector, and provides some extras.

  * •

marf.Storage.StorageManager provides basic implementation of the (possibly
compressed) object serialization, and in our case the GIPC and GEE are storage
manager with respect to a compiled GIPSY program.

  * •

marf.util.Logger is primarily used by the Regression application to log
standard output before calling GIPC or GEE to a file, for future comparison
with an expected output.

  * •

marf.util.Debug is used in many places for debugging convenience allowing to
issue debug messages only if the debug mode is globally on, which is also
maintained within the class.

#####  4.2.2.3 Servlets API

The Java Servlets technology from Sun [Mic05a] was used to implement the
WebEditor interface outlined earlier. While the actual API specification of
servlets is rather vast, the key used components used here are listed:

  * •

The HttpServlet class is the base for all servlets, including WebEditor.

  * •

The doGet() must be overridden to respond to the GET HTTP requests.

  * •

The doPost() must be overridden to respond to the POST HTTP requests. In our
implementation, doPost() is a simply a wrapper around doGet(), so both GET and
POST requests are handled identically.

####  4.2.3 Architectural Design and Unit Integration

Unit integration according to the initial design decisions of the GIPSY system
and setting up package hierarchy played an important role in the success of
this work. A proposed directory structure (see Appendix C.1) and a
corresponding breakdown of the Java packages (see Appendix C.1) hierarchy are
important to the success of GIPSY, especially for public use. The author of
this work inherited the previous GIPSY iteration without any structure or
packaging and proposed and restructured the system to what it is now.

#####  4.2.3.1 GIPSY

When integrating several components of a large system and redesigning some of
their API, the overall system design has to be considered. In Figure 30 is a
high-level view of the main GIPSY modules. These modules can be run as stand-
alone Java applications or start each other.

Figure 30: GIPSY Main Modules.

  * •

The GIPSY class on the diagram represents a stand-alone server for a client-
server type of application, which is capable of spawning GIPC and GEE upon
client’s request. The prime goal of it is testing of intensional programs that
users can submit online and get the result in case they don’t have the
development environment set up from where they are working.

  * •

The GIPC class when run as a stand-alone application invokes all the
intensional and imperative compilers required and produces a compiled version
of a submitted GIPSY program. Optionally, if requested, GIPC can pass the
compiled program on to GEE for execution. The GIPC along with GEE subsumes
what was previously known as Lucid and Facet defined by Chun Lei Ren in
[Ren02].

  * •

The GEE when run as a stand-alone application, begins demand-driven execution
of a GIPSY program that was either compiled and stored or compiled and passed
from GIPC.

  * •

The Regression class is the main driver for the Regression Testing Suite of
GIPSY, that also calls these modules for regression and unit testing.

#####  4.2.3.2 GIPSY Exceptions Framework

Figure 31: GIPSY Exceptions Framework.

The class diagram describing the GIPSY Exceptions Framework is in Figure 31.
The main exception type is GIPSYException that provides some machinery
encapsulating other exceptions. Every major module, like GIPC, GEE, or RIPE in
GIPSY defines its own sublcass of GIPSYException. By doing this, the
applications using the modules can differentiate the exception types and
handle them appropriately. The NotImplementedException is an easy way to use
to indicate some unimplemented but important stubs, if called. It is a
subclass of RuntimeException because it can happen virtually everywhere and
run-time exceptions do not need to be declared to be thrown or caught. The
GIPCException, GEEException, and RIPEException represent base exception
objects for the corresponding modules; the rest are primarily subclasses of
these.

#####  4.2.3.3 GEE Design

The general overview of GEE is in Figure 32. The several modules under the
gipsy.GEE package carry out a complex GIPSY program execution task. The GEE is
the facade and the main starting point for all of GEE. GEE may act as either
an application on its own or be invoked by the GIPC. For the stand-alone
execution a user has to supply a filename of a valid compiled GIPSYProgram.
This program is loaded and GEE starts the Executor thread to actually execute
it. Before Executor begins the GEE may optionally start the available demand
propagation services, such as local (just threads), RMI, Jini-based and the
like. The Executor while executing the program generates demands for the
identifiers listed in the program and then performs the final calculation
based on the results received. The Executor was formerly known as
XLucidInterpreter and the Java version of which was implemented by Bo Lu in
[Lu04] and reworked to handle sequential threads, arrays, objects, and other
than integer and float data types.

Figure 32: GEE Design.

###### Demand Dispatcher

In Figure 33 is a high-level overview of the DemandGenerator and related
classes. Most of the demand propagation in Jini and JavaSpaces is implemented
by Emil Vassev in [VP05]. The integration part included making sure the
IDemandList interface is consistently used by the DemandGenerator along with
the DemandDispatcherAgent to be compliant to the rest of the GEE. The
IDemandList interface was originally designed by Bo Lu in [Lu04] and
redesigned by the author of this thesis to be implemented by the RMI and
threaded versions of GEE and was formerly known as DemandList. Next, the
temporary class WorkTask was made to implement the ISequentialThread interface
according to the overall GIPSY design for sequential threads. This class is
marked as deprecated (and later on will be removed) as every sequential thread
class is generated by the SequentialThreadGenerator and is different from one
GIPSY program to another. Finally, the LUSException (service look up
exception) and DemandDispatcherException were made to be a part of the GIPSY
Exceptions Framework Section 4.2.3.2 by inheriting from the GEEException. For
further implementation details of the DemandDispatcher please refer to Emil’s
work [VP05].

Figure 33: The Demand Dispatcher Integrated and Implemented based on Jini.

###### Intensional Value Warehouse and Garbage Collection

Figure 34: Integration of the Intensional Value Warehouse and Garbage
Collection.

Intensional Value Warehouse and Garbage Collection were implemented by Lei Tao
in [Tao04]. After integration, his contributions became to look like as shown
in Figure 34. The IValueHouse and its extension IVWInterface are the ones used
by the Executor to communicate to a concrete implementation of a warehouse,
allowing adding/changing warehouse implementations easily without affecting
the Executor. All the exception handling is based on the GEEException.

#####  4.2.3.4 RIPE Design

Figure 35: RIPE Design.

The class diagram describing RIPE is in Figure 35. The RIPE class represents a
facade to the rest of the RIPE modules. It is semi-implemented, as many things
are not clear on this side of the project yet. The only part of RIPE that was
advanced well so far by Yimin Ding in [Din04] is the Data-Flow-Graph (DFG)
editor, which is not implemented in Java. The DFGEditor Java class is meant to
be main Java program acting like a bridge between Java and the LEFTY language,
but did not get implemented yet. The rest of the modules are planned stubs.

#####  4.2.3.5 Data Flow Graphs Integration

Figure 36: DFG Integration Design.

The integration of Yimin Ding’s [Din04] DFG-related work is presented in
Figure 36. The DFGAnalyzer was augmented to implement the ICompiler interface
as it follows the same structure as the rest of our compilers, which compiles
a Lucid code from DFG. The DFGException class, a subclass of GIPCException has
been created to indicate an error situation in the DFG processing.
DFGAnalyzer’s SimpleNode was updated to inherit from
GIPC.intesional.SimpleNode due to vast functionality overlap. The two analyzer
and generator modules have been placed under the GIPC.DFG.DFGAnalyzer and
GIPC.DFG.DFGGenerator packages.

###  4.3 Summary

This chapter presented most of the development effort went into integration,
design, and implementation of JLucid, Objective Lucid, and GICF. User
interfaces (both web and command line) has been outlined. Regression Test
Suite has been introduced. The follow up chapter presents a variety of testing
approaches went into the GIPSY to prove successful integration of the old and
implementation of new modules.

To summarize, Objective Lucid, as opposed to GLU [JD96, JDA97] and JLucid,
provides access to the object members and is real object-oriented hybrid
language. While JLucid may indirectly manipulate objects through pseudo-free
functions, the actual objects are still a “black box” to it.

The GICF and IPLCF gave an ability for an easier integration of intensional
and imperative languages in the GIPSY. The below are the steps one needs to
perform to add a new compiler to the GIPSY:

  * •

create a package where the language compiler will reside (usually under
imperative/LANGUAGE or intensional/SIPL/LANGUAGE.

  * •

add a compiler class that extends either one of IntensionalCompiler,
ImperativeCompiler, or implements one of their superinterfaces

  * •

the code segment and fully qualified class name should be added to either
EImperativeLanguages or EIntensionalLanguages

  * •

optionally implement a custom version of a preprocessor if it is a hybrid
language

  * •

implement translation rules to GIPL if it is a SIPL if it is an intensional
language

  * •

implement proper ST/CP generation for an imperative language according to that
language’s semantics and typing instructions

  * •

implement type mapping table upon the need if it is an imperative language

The above might still sound complex, but it is much more easier and flexible
than before. Additionally, some of the steps can be abstracted and simplified,
but it is impossible to eliminate manual work altogether.

##  Chapter 5 Testing

This chapter addresses the testing aspect of this thesis for the following two
main reasons: integration and refactoring of a variety of the GIPSY modules
including GICF and the development and operation of the two new Lucid dialects
developed in this work, namely JLucid and Objective Lucid. Notice, this
testing is far from comprehensive and does not include testing of the
execution performance of any of the programs and many compilation aspects are
still to be resolved as of this writing (and be resolved in the final
version). This is, however, a starting point of setting up the GIPSY testing
infrastructure for the projects to come to do mandatory systematic tests,
which are now a necessity given the size of the system, a centralized source
tree, and the number of subprojects developed simultaneously.

###  5.1 Regression Testing

####  5.1.1 Introduction

The regression testing is a comprehensive set of tests for the implementation
and integration of the GIPSY modules. They test most of the operations and
capabilities of the GIPSY. The test cases primarily are various intensional
programs (hybrid or not) that exercise the main modules, such as GIPC and GEE
as well as their submodules with the major focus on GIPC.

####  5.1.2 Regression Testing Suite

The regression tests can be run against already pre-compiled gipsy.jar, or by
using a temporary installation within the source tree using the Regression
application. Next, there are a “sequential” and “parallel” modes to run the
tests. In the sequential mode tests run in strict sequence, whereas in the
parallel mode multiple threads are started to run groups of tests in parallel.

#####  5.1.2.1 Unit Testing with JUnit

The core of the Regression application is based on the JUnit framework
introduced in Section 2.6.1.3. Regression represents a TestSuite, that
contains ParallelTestCase and SequentialTestCase, a subclasses of TestCase.
Both types of tests are customizable based on the options supplied to the
Regression application (see Section 4.2.1.6). JUnit helps to tell us what
errors happened and in which modules and the reason of the failures
dynamically at run-time.

#####  5.1.2.2 Unit Testing with diff

It becomes cumbersome to use JUnit for all possible cases, in a large system,
where often we are generally interested in the output behaviour changes only.
Here the Unix tool diff helps us. A collection of hand-checked outputs are
said to be “expected”, one ore more file for each test case. Then, when the
next time the test is run, a current directory is created with the current
outputs, and the current and expected output directories are compared with the
diff to show the differences in the output produced by the modules. This is
all achieved by the regression script.

#####  5.1.2.3 Tests

The actual test cases in the form of GIPL, Indexical Lucid, Objective Lucid,
JLucid, and GIPSY programs, are located under the corresponding src/tests/*
directories in the source tree in the form of *.ipl files. These comprise most
of the examples presented earlier in this work as well as developed in
[Paq99], [Ren02], [Wu02], and [Lu04]. The regression tests for the DFG
generation ([Din04]), Intensional Value Warehouse and Garbage Collector
[Tao04] and Demand Migration System (DMS) [VP05] are not present as of this
implementation.

###  5.2 Portability Testing

GIPSY has been tested and is known as expected (regression tests pass) to run
on Red Hat Linux 9, Fedora Core 2, Mac OS X, Solaris 9, Windows 98SE/2000/XP
systems under JDK 1.4 and 1.5. The corresponding hardware architectures were
Intel or Intel-compatible processors (Pentium II, III, and IV with 233 MHz to
1.4 GHz) and G3 and G4 processors from Apple and IBM. For the WebEditor
interface, Tomcat 5 on Mac OS X were tested, but it is believed to run on
other platforms the Jakarta Tomcat runs on.

###  5.3 Solving Problems

This section is targeting some common problems of synchronization in parallel
and distributed environment and how they are solved using the GIPSY system
relieving the programmer from the need of explicitly synchronize the objects.
They also illustrate the use of arrays and embedded Java, and Java objects.
These programs are among many other test cases from the Regression Tests
Suite.

####  5.3.1 Prefix Sum

    pseudocode (for thread ’j’)

    ’shared’  a ’future’ ’int’ ’array’ [1..logP, 1..P] := undefined;
    ’private’ sum ’int’ := j,
              hop ’int’ := 1;

    ’do’ level = 1, logP  --->
        ’if’ j <= P - hop ---> a[level, j] := sum        ’fi’
        ’if’ j >      hop ---> sum +:= a[level, j - hop] ’fi’
         hop := 2 * hop
    ’od’

Figure 1: Pseudocode of a thread $j$ for the Prefix Sum Problem.

    /*
     * PREFIX SUM in GIPL-style JLucid program.
     * Numbers are from 1 to 8.
     * S[I] will contain prefix sum for number ’i’
     */

    #JLUCID

    // Array of prefix sums
    S[8] @d 8
    where
        dimension d;

        S[I] = if(#d = 0)
                    then 1
                    else (2 * S[I] - 1) @d (#d - 1)
               fi;

        // Index the array varies within.
        I @i 8
        where
            dimension i;
            I = if(#i = 0) 1 else (I - 1) @d (#i - 1);
        end;
    end;

Figure 2: The Prefix Sum Problem in JLucid in GIPL Style.

    /*
     * PREFIX SUM in Indexical Lucid-style JLucid
     */

    #JLUCID

    S[8] @d 8
    where
        dimension d;

        S[I] = 1 fby.d (2 * S[I] - 1);

        I @i 8
        where
            dimension i;
            I = 1 fby.i (I - 1);
        end;
    end;

Figure 3: The Prefix Sum Problem in JLucid in Indexical Lucid Style.

The pseudocode of for a thread $j$ is in Figure 1 [Pro03a]. The Figure 2 shows
the program translated into Lucid. The Figure 3 shows the program translated
into Indexical Lucid for numbers from 1 to 8. Below is an equivalent
implementation of the problem (targeting only TLP) in Java; compare the
program’s line count and complexity to that of JLucid:

    // Modified from Dr. Probst’s Cyclic.java
    public class PrefixSum
    {
        public static final int P     = 8; // number of workers
        public static final int logP  = 3; // number of rows in logP x P matrix

        // For permutation of workers
        private static int[] col = {3, 6, 5, 7, 4, 2, 1, 0};

        // These two mimic a 2D array of future variables
        public static int[][]       a       = new int      [logP][P];
        public static Semaphore[][] futures = new Semaphore[logP][P];

        // The resulting sums are to be placed here.
        public static int[]         sums    = new int[P];

        public static void main(String[] argv)
        {
            Worker w[] = new Worker[P];

            for(int j = 0; j < futures.length; j++ )
                for(int k = 0; k < futures[j].length; k++)
                    futures[j][k] = new Semaphore(0);

            for(int j = 0; j < P; j++)
            {
                w[col[j]] = new Worker(col[j] + 1);
                w[col[j]].start();
            }

            for(int j = 0; j < P; j++)
            {
                try
                {
                    w[j].join();
                }
                catch(InterruptedException e)
                {
                }
            }

            for(int j = 0; j < P; j++)
                System.out.println ("Prefix Sum of " + (j + 1) + " = " + sums[j]);

            System.out.println ("System terminates normally.");
        }
    }

    class Semaphore
    {
        private int value;

        Semaphore(int value1)
        {
            value = value1;
        }

        public synchronized void Wait()
        {
            try
            {
                while(value <= 0)
                {
                    wait();
                }

                value--;
            }
            catch (InterruptedException e)
            {
            }
        }

        public synchronized void Signal()
        {
            ++value;
            notify();
        }
    }

    class Worker extends Thread
    {
        private int j;
        private int sum;
        private int hop = 1;

        public Worker(int col)
        {
            sum = j = col;
        }

        public void run()
        {
            System.out.println("Worker " + j + " begins execution.");
            yield();

            for(int level = 0; level < PrefixSum.logP; level++)
            {
                if(j <= PrefixSum.P - hop)
                {
                    System.out.println
                    (
                        "Worker " + j +
                        " defines a[" + level + "," + (j-1) +"]."
                    );

                    PrefixSum.a[level][j - 1] = sum;
                    PrefixSum.futures[level][j - 1].Signal();
                }

                if(j > hop)
                {
                    PrefixSum.futures[level][j - 1 - hop].Wait();

                    System.out.println
                    (
                        "Worker " + j +
                        " uses a[" + level + "," + (j - 1 - hop) + "]."
                    );

                    sum += PrefixSum.a[level][j - 1 - hop];
                }

                hop = 2 * hop;
            }

            PrefixSum.sums[j - 1] = sum;
            System.out.println ("Worker " + j + " terminates.");
        }
    }

####  5.3.2 Dining Philosophers

Below is a JLucid implementation of the Dining Philosophers problem [Dij65,
Dij71, Gin90]. We have arrays of 8 philosophers and 8 forks, each represented
as integers. A philosopher is either thinking (1) or eating (2); likewise for
forks, taken or not. A philosopher may eat when they have exactly two forks,
not less, if the forks are available. If none available, the philosopher waits
(implicit, guaranteed by the GEE). The special variable $I$ serves as an
intensional index for our arrays.

    /**
     * Dining Philosophers Problem
     * in JLucid
     *
     * @author Serguei Mokhov<EMAIL_ADDRESS>     * @version $Revision: 1.10 $ $Date: 2005/03/02 02:57:31 $
     */

    #funcdecl

    int getIninitalRandomState();
    boolean chew(int);
    boolean brainstormIdea(int);

    #JLUCID

    /*
     * Assume 8 philosophers and two states.
     * States: 2 - eating, 1 - thinking
     * Forks are either available or not; hence, 2 states as well.
     */
    PHILOSOPHERS[8] @states 2
    where
        dimension states;

        // Initialize all forks
        FORKS[8] @availability 2
        where
            dimension availability;

            FORKS[I] = getIninitalRandomState();

            I @d 8
            where
                dimension d;
                I = 1 fby.d (I - 1);
            end;
        end;

        /*
         * Run the actual algorithm.
         * NOTE: in this implementation the computation
         * never terminates (normally). It is an infinite loop.
         */
        PHILOSOPHERS[I] =
            if(#states == 1) then
                eat(I) @states 2

                eat(I) =
                    getForks(I) && chew(I);

                getForks(I) = g(l, r)
                where
                    l = FORK[I] @availability 1;
                    r = FORK[I] @availability 1;
                end;
            else
                think(I) @states 1

                think(I) =
                    putForks(I) && brainstormIdea(I);

                putForks(I) = p(l, r)
                where
                    l = FORK[I] @availability 2;
                    r = FORK[I] @availability 2;
                end;
            fi;

        I @d 8
        where
            dimension d;
            I = 1 fby.d (I - 1);
        end;
    end;

    #JAVA

    int getIninitalRandomState()
    {
        // Either 1 or 2
        return new Random().nextInt(2) + 1;
    }

    boolean chew(int i)
    {
        try
        {
            System.out.println("Philo " + i + " is chewing smth tasty now.");
            sleep(new Random().nextInt(i * 1200));
            System.out.println("Philo " + i + " finished chewing.");
            return true;
        }
        catch(InterruptedException e)
        {
            return false;
        }
    }

    boolean brainstormIdea(int i)
    {
        try
        {
            System.out.println("Philo " + i + " is heavily thinking now.");
            sleep(new Random().nextInt(i * 1200));
            System.out.println("Philo " + i + " finished thinking.");
            return true;
        }
        catch(InterruptedException e)
        {
            return false;
        }
    }

####  5.3.3 Fast Fourier Transform

This is an example on how one would compute Fast Fourier Transform (FFT) in
the GIPSY for an array of double values. This is straightforward in Lucid
because it’s deterministic with plenty of parallelism. A JLucid program
implementing FFT is in Section 5.3.3.1. The algorithm is based on the Java
algorithm implemented in MARF [MCSN05, Pre93, Ber05], a code fragment of which
is in Section 5.3.3.2, originally written by Stephen Sinclair. The JLucid
version omits the imaginary part of the transform, but it would not be hard to
add it.

#####  5.3.3.1 Fast Fourier Transform in JLucid.

    /*
     * FFT implementation in JLucid.
     * Serguei Mokhov
     * $Id: fft.ipl,v 1.2 2005/08/13 01:37:23 mokhov Exp $
     */

    #funcdecl
    double sin(double);
    double pi();

    #JAVA

    double sin(double pdValue)
    {
        return Math.sin(pdValue);
    }

    double pi()
    {
        return Math.PI;
    }

    #JLUCID

    A
    where
        // A is an array of 9 FFT values with a
        // normal FFT applied to the array below.

        A = fft([1, 2, 3, 4, 6, 7, 8, 9], 9, 1);

        fft(inputValues, length, sign) = fftValues
            where
                fftValues = apply(length, reverse(length, inputValues), sign);

                apply(len, coeffs, direction) = coeffs @.s (N - 1)
                    where
                        dimension s;

                        N = 2 * len;
                        mmax = (2 fby.s istep) upon(mmax < N);

                        coeffs[J / 2] = coeffs[I / 2] - tempr;
                        coeffs[I / 2] = coeffs[I / 2] + tempr;

                        where
                            istep = mmax fby.s (istep) * 2;

                            M @.m mmax
                            where
                                dimension m;

                                M = (0 fby.m (M + 2)) upon (M < mmax);

                                tempr = wr * coeffs[J / 2] - wi * coeffs[J / 2];

                                J = I + mmax;

                                wr = 1.0 fby.m ((wtemp = wr) * wpr - wi * wpi + wr);
                                wi = 0.0 fby.m (wi * wpr + wtemp * wpi + wi);

                                where
                                    dimension i;
                                    I = (M fby.i (I + istep)) upon (I < N);
                                    theta = (direction * 2 * pi()) / mmax;
                                    wtemp = sin(0.5 * theta);
                                    wpr   = -2.0 * wtemp * wtemp;
                                    wpi   = sin(theta);
                                end;
                            end;
                        end;
                    end;

                // Binary reversion
                reverse(l, vals) = out @.i length
                    where
                        dimension i;
                        out[t] = vals[#.i] @ (#.i + 1) @.bit maxbits(length);
                        where
                            dimension bit;

                            t = 0 fby.bit ((t * 2) | (n & 1));
                            n = #i fby.bit (n / 2);
                        end;
                    end;

                // Determine max number of bits
                maxbits(len) = (mbits - 1) @.m 16
                    where
                        dimension m;

                        mbits = ( 0 fby.m (mbits + 1) ) upon (mbits < 16 && n != 0);
                        n = len fby.m (n / 2);
                    end;
            end;
    end;

    // EOF

#####  5.3.3.2 Fast Fourier Transform code fragment in Java from MARF.

    ...
            /**
             * <p>FFT algorithm, translated from "Numerical Recipes in C++" that
             * implements the Fast Fourier Transform, which performs a discrete Fourier transform
             * in O(n*log(n)).</p>
             *
             * @param InputReal InputReal is real part of input array
             * @param InputImag InputImag is imaginary part of input array
             * @param OutputReal OutputReal is real part of output array
             * @param OutputImag OutputImag is imaginary part of output array
             * @param direction Direction is 1 for normal FFT, -1 for inverse FFT
             * @throws MathException if the sizes or direction are wrong
             */
            public static final void doFFT
            (
                final double[] InputReal,
                double[] InputImag,
                double[] OutputReal,
                double[] OutputImag,
                int direction
            )
            throws MathException
            {
                // Ensure input length is a power of two
                int length = InputReal.length;

                if((length < 1) | ((length & (length - 1)) != 0))
                    throw new MathException("Length of input (" + length + ") is not a power of 2.");

                if((direction != 1) && (direction != -1))
                    throw new MathException("Bad direction specified.  Should be 1 or -1.");

                if(OutputReal.length < InputReal.length)
                    throw new MathException("Output length (" + OutputReal.length + ") < Input length (" + InputReal.length + ")");

                // Determine max number of bits
                int maxbits, n = length;

                for(maxbits = 0; maxbits < 16; maxbits++)
                {
                    if(n == 0) break;
                    n /= 2;
                }

                maxbits -= 1;

                // Binary reversion & interlace result real/imaginary
                int i, t, bit;

                for(i = 0; i < length; i++)
                {
                    t = 0;
                    n = i;

                    for(bit = 0; bit < maxbits; bit++)
                    {
                        t = (t * 2) | (n & 1);
                        n /= 2;
                    }

                    OutputReal[t] = InputReal[i];
                    OutputImag[t] = InputImag[i];
                }

                // put it all back together (Danielson-Lanczos butterfly)
                int mmax = 2, istep, j, m;                                // counters
                double theta, wtemp, wpr, wr, wpi, wi, tempr, tempi;    // trigonometric recurrences

                n = length * 2;

                while(mmax < n)
                {
                    istep = mmax * 2;
                    theta = (direction * 2 * Math.PI) / mmax;
                    wtemp = Math.sin(0.5 * theta);
                    wpr   = -2.0 * wtemp * wtemp;
                    wpi   = Math.sin(theta);
                    wr    = 1.0;
                    wi    = 0.0;

                    for(m = 0; m < mmax; m += 2)
                    {
                        for(i = m; i < n; i += istep)
                        {
                            j = i + mmax;
                            tempr = wr * OutputReal[j / 2] - wi * OutputImag[j / 2];
                            tempi = wr * OutputImag[j / 2] + wi * OutputReal[j / 2];

                            OutputReal[j / 2] = OutputReal[i / 2] - tempr;
                            OutputImag[j / 2] = OutputImag[i / 2] - tempi;

                            OutputReal[i / 2] += tempr;
                            OutputImag[i / 2] += tempi;
                        }

                        wr = (wtemp = wr) * wpr - wi * wpi + wr;
                        wi = wi * wpr + wtemp * wpi + wi;
                    }

                    mmax = istep;
                }
            }
    ...

####  5.3.4 Moving Car

A less contrived example of an Objective Lucid program is presented in Figure
4. This is an example where a Car object changes with time. Eliminating $S$,
and ignoring the print call, we have have:

    #typedecl
    Car;

    #JAVA
    public class Car
    {
        public int x = 0;

        public float speed;
        public float speeddrop;
        public float fuel;
        public float fueldrainrate;

        public Car()
        {
            // Assume initially car was already moving.
            speed = 100.0; fuel = 40.5;
            fueldrainrate = 0.018; speeddrop = 0.1;
        }

        // Move by a number of steps assuming constant speed
        // and decelerate when ran out of fuel.
        public Car move(int steps)
        {
            if(fuel > 0)
            {
                fuel -= fueldrainrate * speed * steps;
                x += steps;
            }
            else if(speed > 0)
            {
                x += steps;
                speed -= speeddrop * steps;
            }

            return this;
        }

        public void printCarState()
        {
            System.out.println
            (
                "Speed: " + speed + ", fuel: " + fuel +
                ", drain: " + fueldrainrate + ", x: " + x +
                ", speeddrop: " + speeddrop
            );
        }
    }

    #OBJECTIVELUCID

    (C @.time 15).printCarState()
    where
        C = Car() fby.time S;
        S = C.move(#time);
    end;

Figure 4: Objective Lucid example of a Car object that changes in time.

C @.time 15 where C = Car() fby.time C.move(#.time)

Using the definition of fby gives:

C @.time 15 = (Car() fby.time C.move(#.time)) @.time 15 = if 15 <= 0 then
Car() else (C.move(#.time)) @.time (15 - 1) = C.move(14)

Our intention is that fby will give the sequence:

Car() Car.move(1) Car.move(2) ... Car.move(15)

This will work as follows. When one generates a demand for C.move(15) it’s not
satisfied until C.move(14) is until C.move(13) is … until C.move(1) is until
Car(), so it recurses back and finally the Car() object instance gets
constructed, and then the demands flow from 1 to 15 and the instance already
exists.

The car also does not accelerate indefinitely. It moves until it has enough
fuel, else it returns the car object with its members unmodified. The drop of
speed is also in place when fuel is depleted.

To further illustrate this idea let’s take the existing example of a simpler
problem of natural numbers presented in Figure 8 and convert it into Objective
Lucid as in Figure 6. First, we will present the eduction tree of the natural
numbers problem (see Figure 5, a corrected version of the one produced by
Paquet in [Paq99]) and then transmute it into the eduction tree of the
execution of the equivalent Objective Lucid propgram, as shown in Figure 7.
The program in Figure 6 exhibits the same properties as the Car example, so
the eduction tree will be similar but will take more space. The important
aspect here is to illustrate the difference between demands for STs and their
lazy execution (which is italisized, e.g. N.inc()); thus, the actual
invocation of a ST method happens at a later time after the demand is made so
we avoid not having called constructor prior execution of an instance method.
In the eduction trees the normal arrows correspond to demands made for
expressions and the bullet arrows correspond to the result of evaluation of
the demands, which are also bold and italic. In the Objective Lucid eduction
tree object instance is denoted as ClassName:MemberName:value and the {d:X}
presents the context of evaluation. The result of evaluation of the Objective
Lucid variant is said to be true because, as previously defined, void methods
are mapped to return true and the last expression bit that is evaluated here
is the print() method call of the instance of a Nat32 class, which returns
void.

Figure 5: Eduction Tree for the Natural Numbers Problem.

    #typedecl
    Nat42;

    #JAVA
    class Nat42
    {
        private int n;

        public Nat42()
        {
            n = 42;
        }

        public Nat42 inc()
        {
            n++;
            return this;
        }

        public void print()
        {
            System.out.println("n = " + n);
        }
    }

    #OBJECTIVELUCID

    (N @.d 2).print[d]()
    where
        dimension d;
        N = Nat42[d]() fby.d N.inc[d]();
    end

Figure 6: The Natural Numbers Problem in Objective Lucid. Figure 7: Eduction
Tree for the Natural Numbers Problem in Objective Lucid.

####  5.3.5 Game of Life

The Game of Life [Gar70] would make a good benchmark for the GIPL. Life takes
place on a 2D grid and evolves in time, so it’s a 3D problem. The value of a
cell at time $T+1$ depends on the value of the cell and its 8 neighbours at
time $T$. Thus, there is a high branching factor and the IVW will get plenty
of exercise. Peter Grogono wrote a version in Haskell, which is functional and
lazy but is not concurrent and does not have an IVW. The author of this work
made a version in Indexical Lucid. In Figure 8 is the top-level function. The
Game of Life program is included in the test suite as a good elaborate test
case, but this work does not address any of the performance and efficiency
issues related to the execution and wareshousing, so no measurements have been
done two compare the efficiency of the program with and without the warehouse
nor with the Haskell program.

    life = evolve T initial (conway life) where
        initial = F(\i ->
            if val Y i == 0 && 0 <= val X i && val X i < 5 then 1 else 0)

        conway v = F(\i ->
            let neighbours v =
                ev v (n i) + ev v (ne i) + ev v (e i) + ev v (se i) +
                ev v (s i) + ev v (sw i) + ev v (w i) + ev v (nw i) in
                b2i(neighbours v == 3 || ev v i == 1 && neighbours v == 2))

        evolve d s e = F(\i ->
            if val d i == 0 then ev s i else ev e (prev d i))

        b2i b = if b then 1 else 0

        n i = F(...)

Figure 8: The Life in Haskell.

    #INDEXICALLUCID

    life = evolve(T, initial(T), conway(life, T))
    where
        dimension T;

        evolve(d, u, v) = u fby.d v;

        initial(d) =
            if(Y == 0 && 0 <= X && X < 5) then 1 else 0
            where
                X = 0 fby.d X + 1;
                Y = 0 fby.d Y + 1;
            end;

        conway(d, v) = b2i(neighbours == 3 || (v == 1 && neighbours == 2))
        where
            neighbours = n(d) + ne(d) + e(d) + se(d) + s(d) + sw(d) + w(d) + nw(d);
            where
                n(d)  = v @.(d - 5);
                ne(d) = v @.(d - 4);
                e(d)  = v @.(d + 1);
                se(d) = v @.(d + 6);
                s(d)  = v @.(d + 5);
                sw(d) = v @.(d + 4);
                w(d)  = v @.(d - 1);
                nw(d) = v @.(d - 6);
            end;

            b2i(b) = if(b) then 1 else 0;
        end;
    end;

Figure 9: The Life in Indexical Lucid.

Explanations:

  * •

$\mathit{evolve(d,u,v)}$ allows a value to evolve in the dimension $d$. The
first value of the stream is given by $u$ and subsequent values by $v$.

  * •

$\mathit{initial(d)}$ defines the initial configuration (five ones in the row
0, zeroes everywhere else in the matrix 5-by-5).

  * •

$\mathit{conway(d,v)}$ computes the successor of state $v$. The functions $n$,
$ne$, $e$, $se$, $s$, $sw$, $w$, and $nw$ are “navigators” that find values of
neighbours.

  * •

$\mathit{b2i(d)}$ converts a Boolean to integer to decide the new value of an
entity.

###  5.4 Summary

There were many tests developed and exercised for the GIPSY. This section
attempted to show the reader the most representative ones and how the
Regression Tests Suite works in the GIPSY for the most modules of GIPC and GEE
and how JUnit is applied to make it possible and maintainable. Now, every new
module added to the GIPSY system will have to have a corresponding unit and/or
regression test (or several tests) exercising most of the features of this
module added.

##  Chapter 6 Conclusion

To conclude, it is believed GIPSY is well off the ground and is steadily
getting ready for its first large public release to the research community. It
is becoming a lot more usable not only by a small circle of GIPSY developers,
but also by scientists and researchers from other research groups. Preliminary
testing (see Chapter 5) and results (Section 6.1) give confidence in the
success of an important step for the GIPSY in the are of flexible hybrid
intensional-imperative programming. To summarize, the newly introduced
features for the innovative intensional research platform GIPSY are a valuable
asset allowing us to release GIPSY to the masses and a new release will be
made at the SourceForge.net at http://sf.net/projects/sfgipsy circa the end of
December 2005 - January 2006.

###  6.1 Results

####  6.1.1 Experiments

The experiments conducted on the GIPSY research platform were primarily
design, development, and testing of hybrid programming paradigms by fusing
together intensional and imperative languages. For test experiments please
refer to Chapter 5.

####  6.1.2 Interpretation of Results

After extensive testing of the design and implementation of ideas presented in
Chapter 3 we can see an enhanced, more flexible GIPSY system taking off the
ground. Most of regression tests pass for the developed sample programs with
known errors and failures.

###  6.2 Discussions and Limitations

####  6.2.1 Lack of Hybrid Intensional-Imperative Semantics Proofs

The semantics for the GIPSY Type System was not defined and the one of JLucid
and Objective Lucid was not formally proven to be correct.

####  6.2.2 Genuine Imperative Compilers

The most serious limitation of the current implementation of the hybrid
paradigm is that there are no genuine imperative GIPSY compilers. The Java
wrapper compiler classes merely resort to the external tools from the library
of enumerated tools. This makes overall error checking and reporting
cumbersome. Additionally, this slows down the compilation process.

####  6.2.3 Cross-Language Data Type Mapping

When implementing other imperative language compilers than Java, or a genuine
compiler for Java, a special mapping has to be explicitly established in the
form of TypeMap. We can avoid this for C/C++ with the JNI [Ste05], but not for
other popular languages.

####  6.2.4 Dimension Index Overflow

While this limitation is not directly related to the main topics of this
thesis, it has to be mentioned. In the current implementation of the dimension
type in all Lucid variants is done as a simple Java integer, and as such, is
finite. Thus, incorrectly written Lucid programs or programs that may require
high dimension values may overflow the dimension index rendering execution of
the program incorrect. This limitation is not handled by the GEE nor
constrained in the operational semantics of Lucid.

####  6.2.5 Hybrid-DFG Integration

This thesis does not address placement, rendering, and integration of the
hybrid AST nodes into DFGs.

####  6.2.6 Dealing With Side Effects and Abrupt Termination

As of this implementation, GEE has very limited control over what’s happening
inside the STs in terms side effects, exceptions, non-termination, etc. in the
Java (or other imperative language) code causing it to exit prematurely or to
hang. Likewise, we cannot do warehousing of non-immutable STs due to the side
effects, i.e. when the same arguments are given to an ST may yield a different
result at different invocations. This is serious aspect, which is related to
the development of any future semantics of the hybrid programming languages
and deserves a separate publication.

####  6.2.7 Imperative Function Overloading

It is an error to write the following:

#funcdecl int foo(int); int foo(float); ...

but it shouldn’t be. This is an error in the sense that only the last
declaration is retained due to the way function identifiers are handled, so no
function overloading at this moment is officially supported. The issue of
dealing with the semantics of a type system in which this is possible,
especially if we support multiple imperative PLs, where each may have
potentially its own type system or even paradigm is complex. However, this
feature is nice to have and some practical aspects can be implemented, which
will be a research topic on its own.

####  6.2.8 Cross-Imperative Language Calls

Normally, an ST written say in #JAVA cannot call another ST in say #C. This
limitation is that only the intensional part can make calls to the imperative
functions. This eliminates the need to keep the type mappings between all
possible combinations of the imperative languages and semantics associated
with this.

However, depending on the language, procedures written in the same language
can possibly communicate by calling each other. E.g. in Java, defining free
members and passing state between free functions is possible as nothing is
done to prevent this.

#JAVA int i;
int foo() { return i + 1; }
int bar() { i++; return foo(); }

This is based on the knowledge about the internal implementation i.e. the “int
i;” bit will also be wrapped in the class, so it’d be legal to have it from
the Java’s point of view; however, is considered to be a kludge and non-
portable feature. To be on the safer side, the STs like that should be written
assuming no knowledge of internal state for communication is available.

####  6.2.9 Security

JLucid, Objective Lucid, and GICF opened up doors for very flexible use of
external languages and resources as a part of intensional computation.
Unfortunately, there are security considerations to deal with when embedding a
vulnerable unsigned code from possibly untrusted remote location and then
propagate it to all the workers participating in computation can result
resulting either gaining some unwanted privileges to the attackers or DDoS.

##  Chapter 7 Future Work

The future work to take on will focus in the following areas to either address
the limitations outlined in Section 6.2 or to introduce new features, not
necessarily all related to the topics of this thesis.

  * •

Integration of the Demand Migration System (DMS) [VP05].

  * •

Formal semantic verification from Indexical Lucid through Objective Lucid.

  * •

Placement of hybrid nodes into DFGs.

  * •

Security.

  * •

Trial C compiler with JNI.

  * •

Fully Explore Array Properties.

  * •

Genuine imperative compilers in GICF.

  * •

Introduction functional language compilers.

  * •

Visualization and control of communication patterns and load balancing.

  * •

Target Host Compilation.

  * •

Java wrapper for the DFG Editor of Yimin Ding.