#  Towards Hybrid Intensional Programming with JLucid, Objective Lucid, and
General Imperative Compiler Framework in the GIPSY

Serguei A. Mokhov

###### Abstract

Pure Lucid programs are concurrent with very fine granularity. Sequential
Threads (STs) are functions introduced to enlarge the grain size; they are
passed from server to workers by Communication Procedures (CPs) in the General
Intensional Programming System (GIPSY). A JLucid program combines Java code
for the STs with Lucid code for parallel control. Thus first, in this thesis,
we describe the way in which the new JLucid compiler generates STs and CPs.
JLucid also introduces array support.

Further exploration goes through the additional transformations that the Lucid
family of languages has undergone to enable the use of Java objects and their
members, in the Generic Intensional Programming Language (GIPL), and Indexical
Lucid: first, in the form of JLucid allowing the use of pseudo-objects, and
then through the specifically-designed the Objective Lucid language. The
syntax and semantic definitions of Objective Lucid and the meaning of Java
objects within an intensional program are provided with discussions and
examples.

Finally, there are many useful scientific and utility routines written in many
imperative programming languages other than Java, for example in C, C++,
Fortran, Perl, etc. Therefore, it is wise to provide a framework to facilitate
inclusion of these languages into the GIPSY and their use by Lucid programs. A
General Imperative Compiler Framework and its concrete implementation is
proposed to address this issue.

## Acknowledgments

I would like to thank my supervisor Dr. Joey Paquet and Dr. Peter Grogono for
ever lasting patience and caring guidance throughout the variety of learning
experience and their advices and insightful comments to make these
contributions possible. I would also like to thank my friendly team members
with whom we together were lifting the complex GIPSY system off the ground.
Specifically, I would like to mention Chun Lei Ren, Paula Bo Lu, Ai Hua Wu,
Yimin Ding, Lei Tao, Emil Vassev, and Kai Yu Wan for outstanding team work.
Thanks to Dr. Patrice Chalin for an in-depth introduction to semantics of
programming languages. Thanks to Dr. Sabine Bergler and Dr. Leila Kosseim for
the journey through the internals of natural language processing side related
to this work. Thanks to my beloved Irina for helping me to carry through.

This work has been sponsored by NSERC and the Faculty of Engineering and
Computer Science of Concordia University, Montréal, Québec, Canada. This
document was produced in LaTeX with the guidance of Dr. Grogono’s manual in
[Gro01] and Concordia University LaTeX thesis styling maintained by Steve
Malowany, Stan Swiercz, and Patrice Chalin.

###### Contents

  1. Acknowledgments
  2. 1 Introduction
    1. 1.1 Thesis Statement
    2. 1.2 Contributions
    3. 1.3 Scope of the Thesis
    4. 1.4 Structure of the Thesis
  3. 2 Background
    1. 2.1 Intensional Programming
    2. 2.2 The Lucid Programming Language
      1. 2.2.1 Brief History and The Family
      2. 2.2.2 Indexical Lucid
        1. 2.2.2.1 Streams
        2. 2.2.2.2 Basic Operators
        3. 2.2.2.3 Sequentiality Problem
        4. 2.2.2.4 Random Access to Streams
        5. 2.2.2.5 Definition of Lucid Operators By Means of @ and #
        6. 2.2.2.6 Abstract Syntax of Lucid
        7. 2.2.2.7 Concrete GIPL Syntax
        8. 2.2.2.8 Semantic Rules
        9. 2.2.2.9 Examples of Lucid Programs
      3. 2.2.3 Lucid Now
    3. 2.3 Hybrid Programming
      1. 2.3.1 ML≤
      2. 2.3.2 FC++
      3. 2.3.3 GLU
      4. 2.3.4 GLU#
    4. 2.4 Compiler Frameworks
    5. 2.5 General Intensional Programming System
      1. 2.5.1 Introduction
      2. 2.5.2 Goals
      3. 2.5.3 General Intensional Programming Compiler
      4. 2.5.4 General Eduction Engine
        1. 2.5.4.1 Demand Propagation Resources for the GEE
        2. 2.5.4.2 Synchronization
      5. 2.5.5 Run-time Interactive Programming Environment
    6. 2.6 Tools
      1. 2.6.1 Java as a Programming Language
        1. 2.6.1.1 Java Reflection
        2. 2.6.1.2 Java Native Interface (JNI)
        3. 2.6.1.3 JUnit
      2. 2.6.2 javacc – Java Compiler Compiler
      3. 2.6.3 MARF
      4. 2.6.4 CVS
      5. 2.6.5 Tomcat
      6. 2.6.6 Build System
        1. 2.6.6.1 Makefiles
        2. 2.6.6.2 Eclipse
        3. 2.6.6.3 JBuilder
        4. 2.6.6.4 Ant
        5. 2.6.6.5 NetBeans
      7. 2.6.7 readmedir
    7. 2.7 Summary
  4. 3 Methodology
    1. 3.1 JLucid: Lucid with Embedded Java Methods
      1. 3.1.1 Rationale
        1. 3.1.1.1 Modeling Non-Determinism
        2. 3.1.1.2 Loading Existing Java Code with embed()
        3. 3.1.1.3 The #JAVA and #JLUCID Code Segments
        4. 3.1.1.4 Is JLucid an Intensional Language?
      2. 3.1.2 Syntax
      3. 3.1.3 Semantics
    2. 3.2 Objective Lucid: JLucid with Java Objects
      1. 3.2.1 Rationale
        1. 3.2.1.1 Pseudo-Objectivism in JLucid
        2. 3.2.1.2 Stream of Objects
        3. 3.2.1.3 Pure Intensional Object-Oriented Programming
      2. 3.2.2 Syntax
      3. 3.2.3 Semantics
    3. 3.3 General Imperative Compiler Framework
      1. 3.3.1 Rationale
      2. 3.3.2 Matching Lucid and Java Data Types
      3. 3.3.3 Sequential Thread and Communication Procedure Generation
        1. 3.3.3.1 Java Sequential Threads
        2. 3.3.3.2 Java Communication Procedures
        3. 3.3.3.3 C Sequential Threads and Communication Procedures with the JNI
        4. 3.3.3.4 Worker Aggregator Definition in the Generator-Worker Architecture
    4. 3.4 Summary
      1. 3.4.1 Benefits
      2. 3.4.2 Limitations
  5. 4 Design and Implementation
    1. 4.1 Internal Design
      1. 4.1.1 General Intensional Programming Compiler Framework
        1. 4.1.1.1 General Imperative Compiler Framework
        2. 4.1.1.2 Generalization of a Concrete Implementation
        3. 4.1.1.3 Resolving Generalization Issues and Binary Compatibility
        4. 4.1.1.4 GIPC Preprocessor
        5. 4.1.1.5 GIPSY Type System
        6. 4.1.1.6 GICF Design
        7. 4.1.1.7 Intensional Programming Languages Compiler Framework
        8. 4.1.1.8 Sequential Thread and Communication Procedure Interfaces
        9. 4.1.1.9 GIPC Design
        10. 4.1.1.10 GIPC Class as a Meta Processor
        11. 4.1.1.11 Calling Sequence
        12. 4.1.1.12 Compiling and Linking
        13. 4.1.1.13 Semantic Analyzer
        14. 4.1.1.14 Interfacing GIPC and GEE and Compiled GIPSY Program
      2. 4.1.2 JLucid
        1. 4.1.2.1 Design
        2. 4.1.2.2 Grammar Generation
        3. 4.1.2.3 Free Java Functions and Java Compiler
        4. 4.1.2.4 Arrays
        5. 4.1.2.5 Implementing embed()
        6. 4.1.2.6 Abstract Syntax Tree and the Dictionary
      3. 4.1.3 Objective Lucid
        1. 4.1.3.1 Design
        2. 4.1.3.2 Grammar Generation
        3. 4.1.3.3 Object Instantiation
        4. 4.1.3.4 The Dot-Notation
        5. 4.1.3.5 Abstract Syntax Tree and the Dictionary
        6. 4.1.3.6 Objects as Arrays and Arrays as Objects
    2. 4.2 External Design
      1. 4.2.1 User Interface
        1. 4.2.1.1 WebEditor – A Web Front-End to the GIPSY
        2. 4.2.1.2 GIPSY Command-Line Interface
        3. 4.2.1.3 RIPE Command-Line Interface
        4. 4.2.1.4 GIPC Command-Line Interface
        5. 4.2.1.5 GEE Command-Line Interface
        6. 4.2.1.6 Regression Testing Application Command-Line Interface
      2. 4.2.2 External Software Interfaces
        1. 4.2.2.1 JavaCC API
        2. 4.2.2.2 MARF Library API
        3. 4.2.2.3 Servlets API
      3. 4.2.3 Architectural Design and Unit Integration
        1. 4.2.3.1 GIPSY
        2. 4.2.3.2 GIPSY Exceptions Framework
        3. 4.2.3.3 GEE Design
        4. 4.2.3.4 RIPE Design
        5. 4.2.3.5 Data Flow Graphs Integration
    3. 4.3 Summary
  6. 5 Testing
    1. 5.1 Regression Testing
      1. 5.1.1 Introduction
      2. 5.1.2 Regression Testing Suite
        1. 5.1.2.1 Unit Testing with JUnit
        2. 5.1.2.2 Unit Testing with diff
        3. 5.1.2.3 Tests
    2. 5.2 Portability Testing
    3. 5.3 Solving Problems
      1. 5.3.1 Prefix Sum
      2. 5.3.2 Dining Philosophers
      3. 5.3.3 Fast Fourier Transform
        1. 5.3.3.1 Fast Fourier Transform in JLucid.
        2. 5.3.3.2 Fast Fourier Transform code fragment in Java from MARF.
      4. 5.3.4 Moving Car
      5. 5.3.5 Game of Life
    4. 5.4 Summary
  7. 6 Conclusion
    1. 6.1 Results
      1. 6.1.1 Experiments
      2. 6.1.2 Interpretation of Results
    2. 6.2 Discussions and Limitations
      1. 6.2.1 Lack of Hybrid Intensional-Imperative Semantics Proofs
      2. 6.2.2 Genuine Imperative Compilers
      3. 6.2.3 Cross-Language Data Type Mapping
      4. 6.2.4 Dimension Index Overflow
      5. 6.2.5 Hybrid-DFG Integration
      6. 6.2.6 Dealing With Side Effects and Abrupt Termination
      7. 6.2.7 Imperative Function Overloading
      8. 6.2.8 Cross-Imperative Language Calls
      9. 6.2.9 Security
  8. 7 Future Work
    1. 7.1 Formal Verification of Semantic Rules and the GIPSY Type System
    2. 7.2 Dealing with Data Flow Graphs in Hybrid Programming
    3. 7.3 Security
    4. 7.4 Implementation of the C Compiler in GICF
    5. 7.5 Fully Explore Array Properties
    6. 7.6 Genuine Imperative and Functional Language Compilers
    7. 7.7 Visualization and Control of Communication Patterns and Load Balancing
    8. 7.8 Target Host Compilation
    9. 7.9 The GIPSY Screen Saver
    10. 7.10 The GIPSY Server
  9. A Definitions and Abbreviations
    1. A.1 Abbreviations
  10. B Sequential Thread and Communication Procedure Interfaces
    1. B.1 Sequential Thread Interface
    2. B.2 Communication Procedure Interface
    3. B.3 Generated Sequential Thread Wrapper Class
    4. B.4 Sample Worker’s Implementation
  11. C Architectural Module Layout
    1. C.1 GIPSY Java Packages and Directory Structure
    2. C.2 GIPSY Modules Packaging
  12. D Grammar Generation Scripts for JLucid and Objective Lucid
    1. D.1 jlucid.sh
    2. D.2 JGIPL.sh
    3. D.3 JIndexicalLucid.sh
    4. D.4 ObjectiveGIPL.sh
    5. D.5 ObjectiveIndexicalLucid.sh

###### List of Figures

  1. 1 Concrete Indexical Lucid Syntax
  2. 2 GIPL Expressions
  3. 3 GIPL where Definitions
  4. 4 Concrete GIPL Syntax
  5. 5 Operational Semantics of GIPL
  6. 6 Natural numbers problem in Indexical Lucid.
  7. 7 Natural numbers problem in GIPL.
  8. 8 Indexical Lucid program implementing the merge() function.
  9. 9 The GIPSY Logo representing the distributed nature of GIPSY.
  10. 10 Structure of the GIPSY
  11. 11 Initial Conceptual Design of the GIPC
  12. 12 Conceptual Design of the GEE
  13. 13 Conceptual Design of the RIPE
  14. 14 Tomcat Web Applications Manager
  15. 1 Indexical Lucid program implementing the merge() function.
  16. 2 Indexical Lucid program implementing the merge() function as inline Java method.
  17. 3 Indexical Lucid program implementing the merge() function as embed().
  18. 4 Illustration of the embed() syntax.
  19. 5 Generated corresponding ST to that of Figure 4.
  20. 6 Inline Java function declaration.
  21. 7 Java method declaration split out from the Lucid part.
  22. 8 Natural numbers problem in plain GIPL.
  23. 9 Natural numbers problem with two Java methods calling each other.
  24. 10 Generated Sequential Thread Class.
  25. 11 JLucid Extension to GIPL Syntax
  26. 12 JLucid Extension to Indexical Lucid Syntax
  27. 13 Additional basic semantic rules to support JLucid
  28. 14 Pseudo-objectivism in JLucid.
  29. 15 Using pseudo-free Java functions to access object properties in JLucid.
  30. 16 Objective Lucid example.
  31. 17 Objective Lucid Syntax
  32. 18 Additional basic semantic rules to support Objective Lucid
  33. 19 Hybrid GIPSY Program Compilation Process
  34. 20 Generator-Worker Architecture
  35. 1 Example of a hybrid GIPSY program.
  36. 2 Another example of a hybrid GIPSY program.
  37. 3 Original Framework for the General Intensional Programming Compiler in the GIPSY
  38. 4 Modified Framework for the General Intensional Programming Compiler in the GIPSY
  39. 5 The FormatTag API.
  40. 6 The GIPC Preprocessor.
  41. 7 Preprocessor Grammar for a GIPSY program.
  42. 8 GIPSY Type System.
  43. 9 GICF Design.
  44. 10 IPLCF Design.
  45. 11 SIPL to GIPL Translator Integration.
  46. 12 Sequential Thread and Communication Procedure Class Diagram.
  47. 13 All GIPC Compilers.
  48. 14 Overall GIPC Design.
  49. 15 Sequence Diagram of GIPSY Program Compilation Process.
  50. 16 Sequence Diagram of Intensional Compilation Process.
  51. 17 Sequence Diagram of Imperative Compilation Process.
  52. 18 Semantic Analyzer.
  53. 19 Class diagram describing GIPSYProgram.
  54. 20 JLucid Design.
  55. 21 JLucid Compilation Sequence.
  56. 22 Java Compilation Sequence.
  57. 23 Objective Lucid Design.
  58. 24 Objective Lucid Compilation Sequence.
  59. 25 GIPSY WebEditor Interface.
  60. 26 JavaCC- and JJTree-generated Modules Used by Several GIPC Modules.
  61. 27 MARF Utility Classes used by the GIPSY.
  62. 28 Dictionary and DictionaryItem API
  63. 29 Dictionary Usage within the GIPSY
  64. 30 GIPSY Main Modules.
  65. 31 GIPSY Exceptions Framework.
  66. 32 GEE Design.
  67. 33 The Demand Dispatcher Integrated and Implemented based on Jini.
  68. 34 Integration of the Intensional Value Warehouse and Garbage Collection.
  69. 35 RIPE Design.
  70. 36 DFG Integration Design.
  71. 1 Pseudocode of a thread $j$ for the Prefix Sum Problem.
  72. 2 The Prefix Sum Problem in JLucid in GIPL Style.
  73. 3 The Prefix Sum Problem in JLucid in Indexical Lucid Style.
  74. 4 Objective Lucid example of a Car object that changes in time.
  75. 5 Eduction Tree for the Natural Numbers Problem.
  76. 6 The Natural Numbers Problem in Objective Lucid.
  77. 7 Eduction Tree for the Natural Numbers Problem in Objective Lucid.
  78. 8 The Life in Haskell.
  79. 9 The Life in Indexical Lucid.
  80. 1 Sequential Thread Interface.
  81. 2 Communication Procedure Interface.
  82. 1 GIPSY Java Packages Hierarchy.

###### List of Tables

  1. 1 Matching data types between Lucid and Java.
  2. 1 Correspondence of the GIPSY .jar files and the modules.

##  Chapter 1 Introduction

###  1.1 Thesis Statement

In the previous prototype of the General Intensional Programming System
(GIPSY) there existed limitations to its potential in distributed computing –
lack of sequential threads and communication procedures. Additionally, the
capabilities of Indexical Lucid and GIPL, the primary GIPSY’s languages, were
limited to only computing aspects without input/output, arrays, and some other
essential features (e.g. math, non-determinism, dynamic loading) that exist in
imperative (e.g. Java) languages. We discuss an extension to Generic
Intensional Programming Language (GIPL) and Indexical Lucid with embedded Java
– JLucid. A few problems are solved as an example using the enhanced language.

JLucid brings embedded Java and most of its powers into Indexical Lucid in the
GIPSY by allowing intensional languages to manipulate Java methods as first
class values111The Java methods are not referred to as “functions” as in
functional programming – the Java methods can be passed around as values
inside the Lucid part, but not to or from Java part of a GIPSY program..
However, it is very natural to have objects with Java and manipulate their
members in scientific intensional computation, yet JLucid fails to support
that Java’s capability. Hence, we design Objective Lucid to address this
deficiency. We define the operational semantics of Objective Lucid, and give
some examples of its application.

Existence of JLucid, Objective Lucid, and GLU as well as many useful libraries
written in other imperative languages, such as C/C++, Perl, Python, Fortran
etc. demanded ability to use code written in those languages by intensional
programs, naturally. Thus, we design a first version of the General Imperative
Compiler Framework (GICF) as a part of the GIPSY to allow GIPSY programs to
use virtually any combination of intensional and imperative languages at the
meta level. This is a very ambitious goal; therefore, the proposal is the
first iteration of the framework open for later refinements as it matures
along with the corresponding changes to the run-time system.

###  1.2 Contributions

Primary contributions of this thesis are outlined below:

  * •

JLucid

    * –

Semantics of pseudo-free Java methods in Lucid programs

    * –

Design and implementation of JLucid and its compiler in the GIPSY

  * •

Objective Lucid

    * –

Semantics of the integration of Java objects in Lucid programs

    * –

Design and implementation of the Objective Lucid compiler

  * •

General Imperative Compiler Framework

    * –

Design and Implementation of the GICF

    * –

Embedding of a Java compiler in the GICF

  * •

WebEditor to edit, compile, and run GIPSY programs online

  * •

System Architecture Issues

    * –

Rework and refactoring of most existing system design, both at the
architectural and detailed design levels

    * –

Major rework of the architecture and detailed design of GIPC

    * –

Java sequential threads generation

    * –

Threaded and RMI communication procedures generation

    * –

GIPSY Type System222Though the type system may seem not to be related to the
architecture, but it impacted the design most of the main modules in it, so it
was classified as architectural.

    * –

GIPSY Exceptions Framework

    * –

Regression Testing Infrastructure

    * –

Unit Testing Automation with JUnit

The last contributed items touch the rest of the GIPSY, the components and
modules done by other team members. The integration performed (outside of the
main scope of this thesis) demanded extensive testing. Without the integration
and testing work, these other contributions wouldn’t be possible. This also
includes developing and enforcing Coding Conventions and setting up project’s
CVS repository [Mok05b, Mok03a, Mok03b] for the entire project as this work is
to become a manual for the current and future GIPSY developers and
researchers.

###  1.3 Scope of the Thesis

While the Contributions section outlines the major work done, the below
explains what was not done or exhibits some limitations at the time of this
writing:

  * •

Integrated imperative compilers aren’t native to the GIPSY, instead we call
external compilers, such as javac, gcc, g++, nmake.exe, bc.exe, perl, etc.
depending on a platform.

  * •

Even though the mechanism was designed and implemented to generate CPs and
STs, only two of the concrete implementations of the actual CPs were done: for
local execution and distributed execution by extending the RMI implementation
done by Bo Lu. The other implementations of CPs for Jini, DCOM+, CORBA and
others are being worked on by other team members at the time of this writing.

  * •

Semantic rules to have Java objects in Objective Lucid have been developed,
but have not been formally proven to be correct.

  * •

When presenting GICF and the Preprocessor syntax, no semantic rules are given
for any of parts of the hybrid programs, except for JLucid and Objective
Lucid, i.e. the semantics of integrated Java itself or C constructs, etc.

  * •

JLucid and Objective Lucid are still in their experimental stage of
development and it will take some time before they mature.

###  1.4 Structure of the Thesis

The next chapter provides the necessary background on the Lucid family of
languages, its history, operational semantics, compiler frameworks, and hybrid
programming. Then, it gives the context of this thesis, the GIPSY system, and
the tools and techniques employed to make the contributions possible. The core
of this thesis is based on three publications, namely [MPG05, MP05b, MP05a].
Chapter 3 describes the approach and methodology used to overcome and provide
a solution to the problems stated in Section 1.1. Then, the design
implementation details are presented in Chapter 4. Chapter 5 introduces the
Regression Testing Suite for GIPSY and what kinds of tests were performed and
their limitations. Finally, Chapter 6 and Chapter 7 conclude on the work done,
discuss the results and limitations of the implementation, and lay down some
paths towards enhancing the GIPSY in various areas further. At the end, there
is a list of references, Bibliography, and an Appendix with most common
abbreviations found in this work, CP and ST interfaces, JLucid and Objective
Lucid grammar generation scripts, etc., followed by an overall index.

##  Chapter 2 Background

While there is a complete and comprehensive set of references in the
Bibliography chapter that was a great deal of help to the creation of this
work, there are some keynotes that require special mention. The following are
some of the related readings that were sources of inspiration and invaluable
informational food for thought. These include Joey Paquet’s PhD thesis
“Scientific Intensional Programming” [Paq99], related hybrid intensional-
imperative programming in various GLU-related work, such as [JD96, JDA97],
other recent hybrid programming papers, such as [PK04, MS01, SM02], the PhD
thesis of Paula Bo Lu [Lu04] and other theses of the GIPSY group, such as
[Ren02, Din04, Tao04, Wu02], and semantics of programming languages in
[Gro02a, HJ02, Moe04]. Additionally, since this work also deals with compiler
frameworks, a general overview of existing frameworks is presented. An on-line
encyclopedia, Wikipedia [WSoafaotw05], was a valuable resource for the
background and literature review, some of which is summarized in the sections
that follow.

###  2.1 Intensional Programming

Intensional programming is a generalization of unidimensional contextual (also
known as modal logic [Car47, Kri59, Kri63]) programming such as temporal
programming, but where the context is multidimensional and implicit rather
than unidimensional and explicit. Intensional programming is also called
multidimensional programming because the expressions involved are allowed to
vary in an arbitrary number of dimensions, the context of evaluation is thus a
multidimensional context. For example, in intensional programming, one can
very naturally represent complex physical phenomena such as plasma physics
(e.g. in Tensor Lucid in [Paq99]), which are in fact a set of charged
particles placed in a space-time continuum that behaves according to a limited
set of laws of intensional nature. This space-time continuum becomes the
different dimensions of the context of evaluation, and the laws are expressed
naturally using intensional definitions [Paq99]. Joey Paquet’s PhD thesis
discusses the syntax and semantics of the Lucid language, designs GIPL and
Tensor Lucid. While we omit the Tensor Lucid part, the reader is reminded
about the basic properties of the Indexical Lucid and GIPL languages in the
follow up sections in greater detail to provide the necessary context for the
follow up work in Chapter 3 and Chapter 4.

#### Intensional Logic

Intensional programming (IP) is based on intensional (or multidimensional or
modal) logic (where semantics was applied first by [Car47, Kri59, Kri63]),
which, in turn, are based on Natural Language Understanding (aspects, such as,
time, belief, situation, and direction are considered). IP brings in
dimensions and context to programs (e.g. space and time in physics or
chemistry). Intensional logic adds dimensions to logical expressions; thus, a
non-intensional logic can be seen as a constant or a snapshot in all possible
dimensions. Intensions are dimensions at which a certain statement is true or
false (or has some other than a Boolean value). Intensional operators are
operators that allow us to navigate within these dimensions.

#### Temporal Intensional Logic

Temporal intensional logic is an extension of temporal logic that allows to
specify the time in the future or in the past.

(1) $E_{1}$ := it is raining here today

Context: {place:here, time:today}

(2) $E_{2}$ := it was raining here before(today) = yesterday

(3) $E_{3}$ := it is going to rain at(altitude here \+ 500 m) after(today) =
tomorrow

Let’s take $E_{1}$ from (1) above. Then let us fix here to Montreal and assume
it is a constant. In the month of March, 2004, with granularity of day, for
every day, we can evaluate $E_{1}$ to either true or false:

    Tags:   1 2 3 4 5 6 7 8 9 ...
    Values: F F T T T F F F T ...

If you start varying the here dimension (which could even be broken down into
$X$, $Y$, $Z$), you get a two-dimensional evaluation of $E_{1}$:

    City / Day  1 2 3 4 5 6 7 8 9 ...
    Montreal    F F T T T F F F T ...
    Quebec      F F F F T T T F F ...
    Ottawa      F T T T T T F F F ...

The purpose of this example is to remind the reader the basic ideas behind
intensions and intensional programming and what dimensionality is by using
natural language. What follows is formalization of the above in terms of the
Lucid programming language.

###  2.2 The Lucid Programming Language

Let us begin by introducing the Lucid language history and which features of
it came at different stages of its evolution to its present form. This is the
necessary step to further illustrate the purpose of this thesis.

####  2.2.1 Brief History and The Family

From 1974 to Lucid Today:

  1. 1.

Lucid as a Pipelined Dataflow Language through 1974-1977. Lucid was introduced
by Anchroft and Wadge in [AW76, AW77]. Features:

     * •

A purely declarative language for natural expression of iterative algorithms.

     * •

Goals: semantics and verification of correctness of programming languages (for
details see [AW76, AW77]).

     * •

Operators as pipelined streams: one for initial element, and then all for the
successor ones.

  2. 2.

Intensions, Indexical Lucid, GRanular Lucid (GLU, [JD96, JDA97]), circa 1996.
More details on these two dialects are provided further in the chapter as they
directly relate to the theme of this thesis. Features:

     * •

Random access to streams in Indexical Lucid.

     * •

First working hybrid intensional-imperative paradigm (C/Fortran and Indexical
Lucid) in the form of GLU.

     * •

Eduction or demand-driven execution (in GLU).

  3. 3.

Partial Lucid, Tensor Lucid, 1999 [Paq99].

     * •

Partial Lucid is an intermediate experimental language used for demonstrative
purposes in presenting the semantics of Lucid in [Paq99].

     * •

Tensor Lucid dialect was developed by Joey Paquet for plasma physics
computations to illustrate advantages and expressiveness of Lucid over an
equivalent solution written in Fortran.

  4. 4.

GIPL, 1999 [Paq99].

     * •

All Lucid dialects can be translated into this basic form of Lucid, GIPL
through a set of translation rules. (GIPL is in the foundation of the
execution semantics of GIPSY and its GIPC and GEE because its AST is the only
type of AST GEE understands when executing a GIPSY program).

  5. 5.

RLucid, 1999, [GP99]

     * •

A Lucid dialect for reactive real-time intensional programming.

  6. 6.

JLucid, Objective Lucid, 2003 - 2005

     * •

These dialects introduce a notion of hybrid and object-oriented programming in
the GIPSY with Java and Indexical Lucid and GIPL, and are discussed great
detail in the follow up chapters of this thesis.

  7. 7.

Lucx [WAP05], 2003 - 2005

     * •

Kaiyu Wan introduces a notion of contexts as first-class values in Lucid,
thereby making Lucx the true intensional language.

  8. 8.

Onyx [Gro04], April 2004.

     * •

Peter Grogono makes an experimental derivative of Lucid – Onyx to investigate
on lazy evaluation of arrays.

  9. 9.

GLU# [PK04], 2004

     * •

GLU# is an evolution of GLU where Lucid is embedded into C++.

####  2.2.2 Indexical Lucid

When Indexical Lucid came into existence, it allowed accessing context
properties in multiple dimensions. Prior Indexical Lucid, the only implied
dimension was a set of natural numbers. With Indexical Lucid, we can have more
than one dimension, and we can query for a part of the context (any dimensions
of it). Thus, the syntactic definition has been amended to include an ability
to specify which dimensions exactly we are working on.

#####  2.2.2.1 Streams

Lucid variables and expressions are said to be streams of values, through
which one can navigate using some sort of navigational operators. In the
natural language example given earlier the operators were before(), after(),
and at(); here we begin by introducing first() and next() (very much like in
LISP).

If the following equations hold111Note, these are initial conditions of a
definition to illustrate the ideas behind the streams and not an actual
declaration of constructs in the language one would normally write.:

  * •

first $X=0$

  * •

next $X=X+1$ (like succ in LISP)

where $0$ is a stream of 0’s: $(0,0,0,...,0,...)$. Likewise, $1$ is a stream
of 1’s, and the ‘$+$’ operator performs pair-wise addition of the elements in
the streams according to the implied current dimension index. Thus, $X$ is
defined as a stream, such that:

  * •

$x_{0}=0,x_{i+1}=x_{i}+1$, or

  * •

$X=(x_{0},x_{1},...,x_{i},...)=(0,1,...,i,...)$

Similarly, if:

  * •

first $X=X$

  * •

next $Y=Y+$ next $X$

$Y$ here becomes a running sum of $X$:

  * •

$y_{0}=x_{0};y_{i+1}=y_{i}+x_{i+1}$

  * •

$Y=(y_{0},y_{1},...,y_{i},...)=(0,1,...,i(i+1)/2,...)$

#####  2.2.2.2 Basic Operators

This section defines properties of basic Lucid operators, which were proven by
Paquet in [Paq99].

###### Operator fby.

Operator fby stands for “followed by”. fby allows simply to suppress dimension
index and switch to another stream. As an example the previously shown streams
$X$ and $Y$ can be defined as follows using fby:

  * •

$X=0$ fby $X+1=(0,1,2,...,i,...)$

  * •

$Y=X$ fby $Y+$ next $X=(0,1,...,i(i+1)/2,...)$

To provide an analogy to lists, we can say that that the following operators
are equivalent:

  * •

first and hd

  * •

next and tl

  * •

fby and cons

###### Informal Definition of first, next, fby.

  * •

Definitions:

    * –

first $X=(x_{0},x_{0},...,x_{0},...)$

    * –

next $X=(x_{1},x_{2},...,x_{i+1},...)$

    * –

$X$ fby $Y=(x_{0},y_{0},y_{1},...,y_{i-1},...)$

  * •

These are the three operators of the original Lucid.

  * •

Indexical Lucid has come into existence with the ability to access an
arbitrary element by some index $i$ in the stream.

###### Operators wvr, asa, and upon.

The other three operators that are slightly more complex informally defined
below:

  * •

$X$ wvr $Y=$

if first $Y\neq 0$

then $X$ fby (next $X$ wvr next $Y)$

else (next $X$ wvr next $Y)$

  * •

$X$ asa $Y=$ first $(X$ wvr $Y)$

  * •

$X$ upon $Y=$

$X$ fby

(if first $Y\neq 0$ then $($next $X$ upon next $Y)$ else $(X$ upon next $Y))$

where wvr stands for whenever, asa stands for as soon as and upon stands for
advances upon. wvr chooses from its left-hand-side operand only values in the
current dimension where the right-hand-side evaluates to true. asa returns the
value of its left-hand-side as a first point in that stream as soon as the
right-hand-side evaluates to true. Unlike asa, upon switches context of its
left-hand-side operand uf the right-hand side is true.

#####  2.2.2.3 Sequentiality Problem

With tagged-token dataflows of the original Lucid operators one could only
define an algorithm with pipelined, or sequential, data flow:

  * •

It is wasteful use of computing resources (e.g. to compute an element $i$ we
need $i-1$, but $i-1$ may never be used/needed otherwise).

  * •

Sequential access to the stream of values.

#####  2.2.2.4 Random Access to Streams

New intensional operators are introduced to remedy the sequentiality problem:
@ and #. The operators are used as an index # corresponding to the current
position that allows querying the current context, and @ is intensional
navigation to switch the context. With @ and #:

  * •

the computation is defined according to a context (here a single integer),

  * •

Lucid is no longer a data-flow language and is on the road to intensional
programming, and

  * •

the previously introduced intensional operators can be redefined in terms of
the operators # and @.

In terms of the three original operators of first, next, and fby the operators
@ and # are defined as follows:

Definition 1

$\\#=0$ fby $(\\#+1)$

$X@Y=$ if $Y=0$ then first $X$ else (next $X)@(Y-1)$

Both $X$ and $Y$ in the above definition are variable streams, and their
current values are determined by their current context at the time of
evaluation. To redefine the meaning of @ and # Paquet uses the denotational
form, with the following proposition:

Proposition 1

(1) $[\\#]_{i}=i$

(2) $[X@Y]_{i}=[X]_{[Y]_{i}}$

where (1) means the value of # at the current context $i$ is $i$ itself (i.e.
we query the value of our current dimension), and (2) says that evaluate $Y$
at the current context $i$ and then use $Y$ as a new context for $X$.

#####  2.2.2.5 Definition of Lucid Operators By Means of @ and #

First we present the definition of the operators via @ and # denoted in
monospaced font, and then we will provide their equivalence to the original
Lucid operators, denoted as small caps.

Definition 2

(1) first $X$ = $X@0$

(2) next $X=X@(\\#+1)$

(3) $X$ fby $Y=$ if # $=0$ then $X$ else $Y@(\\#-1)$

(4) $X$ wvr $Y=X@T$ where

$T=U$ fby $U@(T+1)$

$U=$ if $Y$ then # else next $U$

end

(5) $X$ asa $Y=$ first $(X$ wvr $Y)$

(6) $X$ upon $Y=X@W$

where $W=0$ fby (if $Y$ then $(W+1)$ else $W)$ end

#####  2.2.2.6 Abstract Syntax of Lucid

Abstract and concrete syntaxes of Lucid for expressions, definitions, and
operators are presented in Figure 2, Figure 3, and Figure 1 for both Indexical
Lucid and GIPL.

op | $::=$ | intensional-op
---|---|---
| $|$ | data-op
intensional-op | $::=$ | i-unary-op
| $|$ | i-binary-op
i-unary-op | $::=$ |  first $|$ next $|$ prev
i-binary-op | $::=$ |  fby $|$ wvr $|$ asa $|$ upon
data-op | $::=$ | unary-op
| $|$ | binary-op
unary-op | $::=$ | ! $|$ $-$ $|$ iseod
binary-op | $::=$ | arith-op
| $|$ | rel-op
| $|$ | log-op
arith-op | $::=$ |  $+$ $|$ $-$ $|$ $*$ $|$ $/$ $|$ %
rel-op | $::=$ |  $<$ $|$ $>$ $|$ $<=$ $|$ $>=$ $|$ $==$ $|$ $!=$
log-op | $::=$ |  && $|$ ||
Figure 1: Concrete Indexical Lucid Syntax $E$ | $::=$ | $id$
---|---|---
| $|$ | $E(E_{1},...,E_{n})$
| $|$ |  if $E$ then $E^{\prime}$ else $E^{\prime\prime}$
| $|$ | $\\#E$
| $|$ | $E@E^{\prime}E^{\prime\prime}$
| $|$ |  $E$ where $Q$
Figure 2: GIPL Expressions $Q$ | $::=$ |  dimension $id$
---|---|---
| $|$ | $id=E$
| $|$ | $id(id_{1},id_{2},...,id_{n})=E$
| $|$ | $QQ$
Figure 3: GIPL where Definitions

#####  2.2.2.7 Concrete GIPL Syntax

The GIPL is the generic programming language of all intensional languages,
defined by the means of only two intensional operators – @ and #. It has been
proven that other intensional programming languages of the Lucid family can be
translated into the GIPL [Paq99]. The concrete syntax of the GIPL is presented
in Figure 4. It has been amended to support the isoed operator of Indexical
Lucid for completeness and influenced by the productions from Lucx [WAP05] to
allow contexts as first-class values while maintaining backward compatibility
to the GIPL language designed by Paquet in [Paq99].

               E  ::=   id
                   |    E(E,...,E)                      #LUCX
                   |    E[E,...,E](E,...,E)             #GIPL
                   |    if E then E else E fi
                   |    # E
                   |    E @ [E:E]                       #GIPL
                   |    E @ E                           #LUCX
                   |    E where Q end;
                   |    [E:E,...,E:E]                   #LUCX
                   |    iseod E;                        #INDEXICAL
               Q  ::=   dimension id,...,id;
                   |    id = E;
                   |    id(id,....,id) = E;             #LUCX
                   |    id[id,...,id](id,....,id) = E;  #GIPL
                   |    QQ

Figure 4: Concrete GIPL Syntax

#####  2.2.2.8 Semantic Rules

Paquet’s PhD thesis [Paq99] presents details of the operational semantics of
GIPL recited here for the unaware reader with a brief description. Figure 5
provides initial operational semantic rules for Indexical Lucid in Hoare Logic
[Moe04, HJ02]. Later on, these rules are extended to support free Java methods
and Java objects in JLucid and Objective Lucid respectively in Chapter 3.

###### Notation

  * •

$\mathcal{D}$ represents the definition environment where all symbols are
defined (a dictionary of identifiers).

  * •

$\mathcal{D},\mathcal{P}\vdash E:a$ represents current context of evaluation
(a set of dimensions $\mathcal{P}$) and the dictionary that yields a specified
result $a$ under that context given expression $E$.

  * •

const, op, dim, func, and var represent what kind of construct types are put
into $\mathcal{D}$ as constants, operators, dimensions, functions, and
variables respectively.

  * •

the $\mathbf{E_{Xid}}$ type of rules place different identifier types listed
above into the definition environment $\mathcal{D}$.

  * •

the remaining $\mathbf{E_{xyz}}$-style rules correspond to the execution (or
rather application of) of the operators, functions, and conditionals to their
argument expressions given the definition of them in $\mathcal{D}$ and the
current context. Thus, $\mathbf{E_{op}}$ specifies application of a defined
operator function $f$ in the current context to its arguments (usually one for
unary operators and two for binary); $\mathbf{E_{fct}}$ applies the named
function to its arguments translating the formal arguments to actual;
$\mathbf{E_{c_{T}}}$ and $\mathbf{E_{c_{F}}}$ correspond to conditional
evaluation of the then and else branching clauses; $\mathbf{E_{at}}$ and
$\mathbf{E_{tag}}$ correspond to the universal intensional operators @ and #
for switching of and querying for the current context; and $\mathbf{E_{w}}$
corresponds to the scope definition marked by the where clause.

  * •

the $\mathbf{Q}$-style rules allow definitions within the scope of the
dimension $\mathbf{Q_{dim}}$ and variable identifier $\mathbf{Q_{id}}$ types
and their composition.

$\displaystyle{\mathbf{E_{cid}}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D}(\textit{id})=(\texttt{const},c)}{\mathcal{D},\mathcal{P}\vdash\textit{id}:c}$
$\displaystyle{\mathbf{E_{opid}}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D}(\textit{id})=(\texttt{op},f)}{\mathcal{D},\mathcal{P}\vdash\textit{id}:\textit{id}}$
$\displaystyle{\mathbf{E_{did}}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D}(\textit{id})=(\texttt{dim})}{\mathcal{D},\mathcal{P}\vdash\textit{id}:\textit{id}}$
$\displaystyle{\mathbf{E_{fid}}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D}(\textit{id})=(\texttt{func},\textit{id}_{i},E)}{\mathcal{D},\mathcal{P}\vdash\textit{id}:\textit{id}}$
$\displaystyle{\mathbf{E_{vid}}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D}(\textit{id})=(\texttt{var},E)\qquad\mathcal{D},\mathcal{P}\vdash
E:v}{\mathcal{D},\mathcal{P}\vdash\textit{id}:v}$
$\displaystyle{\mathbf{E_{op}}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D},\mathcal{P}\vdash
E:\textit{id}\qquad\mathcal{D}(\textit{id})=(\texttt{op},f)\qquad\mathcal{D},\mathcal{P}\vdash
E_{i}:v_{i}}{\mathcal{D},\mathcal{P}\vdash
E(E_{1},\ldots,E_{n}):f(v_{1},\ldots,v_{n})}$
$\displaystyle{\mathbf{E_{fct}}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D},\mathcal{P}\vdash
E:\textit{id}\qquad\mathcal{D}(\textit{id})=(\texttt{func},\textit{id}_{i},E^{\prime})\qquad\mathcal{D},\mathcal{P}\vdash
E^{\prime}[\textit{id}_{i}\leftarrow E_{i}]:v}{\mathcal{D},\mathcal{P}\vdash
E(E_{1},\ldots,E_{n}):v}$ $\displaystyle{\mathbf{E_{c_{T}}}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D},\mathcal{P}\vdash
E:\textit{true}\qquad\mathcal{D},\mathcal{P}\vdash
E^{\prime}:v^{\prime}}{\mathcal{D},\mathcal{P}\vdash\mathtt{if}\;E\;\mathtt{then}\;E^{\prime}\;\mathtt{else}\;E^{\prime\prime}:v^{\prime}}$
$\displaystyle{\mathbf{E_{c_{F}}}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D},\mathcal{P}\vdash
E:\textit{false}\qquad\mathcal{D},\mathcal{P}\vdash
E^{\prime\prime}:v^{\prime\prime}}{\mathcal{D},\mathcal{P}\vdash\mathtt{if}\;E\;\mathtt{then}\;E^{\prime}\;\mathtt{else}\;E^{\prime\prime}:v^{\prime\prime}}$
$\displaystyle{\mathbf{E_{tag}}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D},\mathcal{P}\vdash
E:\textit{id}\qquad\mathcal{D}(\textit{id})=(\texttt{dim})}{\mathcal{D},\mathcal{P}\vdash\\#E:\mathcal{P}(\textit{id})}$
$\displaystyle{\mathbf{E_{at}}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D},\mathcal{P}\vdash
E^{\prime}:\textit{id}\qquad\mathcal{D}(\textit{id})=(\texttt{dim})\qquad\mathcal{D},\mathcal{P}\vdash
E^{\prime\prime}:v^{\prime\prime}\qquad\mathcal{D},\mathcal{P}\\!\dagger\\![\textit{id}\mapsto
v^{\prime\prime}]\vdash E:v}{\mathcal{D},\mathcal{P}\vdash
E\;@E^{\prime}\;E^{\prime\prime}:v}$ $\displaystyle{\mathbf{E_{w}}}$
$\displaystyle:$ $\displaystyle\frac{\mathcal{D},\mathcal{P}\vdash
Q\>:\>\mathcal{D}^{\prime},\mathcal{P}^{\prime}\qquad\mathcal{D}^{\prime},\mathcal{P}^{\prime}\vdash
E:v}{\mathcal{D},\mathcal{P}\vdash E\;\mathtt{where}\;Q:v}$
$\displaystyle{\mathbf{Q_{dim}}}$ $\displaystyle:$
$\displaystyle\frac{}{\mathcal{D},\mathcal{P}\vdash\texttt{dimension}\;\textit{id}\>:\>\mathcal{D}\\!\dagger\\![\textit{id}\mapsto(\texttt{dim})],\mathcal{P}\\!\dagger\\![\textit{id}\mapsto
0]}$ $\displaystyle{\mathbf{Q_{id}}}$ $\displaystyle:$
$\displaystyle\frac{}{\mathcal{D},\mathcal{P}\vdash\textit{id}=E\>:\>\mathcal{D}\\!\dagger\\![\textit{id}\mapsto(\texttt{var},E)],\mathcal{P}}$
$\displaystyle{\mathbf{QQ}}$ $\displaystyle:$
$\displaystyle\frac{\mathcal{D},\mathcal{P}\vdash
Q\>:\>\mathcal{D}^{\prime},\mathcal{P}^{\prime}\qquad\mathcal{D}^{\prime},\mathcal{P}^{\prime}\vdash
Q^{\prime}:\mathcal{D}^{\prime\prime},\mathcal{P}^{\prime\prime}}{\mathcal{D},\mathcal{P}\vdash
Q\;Q^{\prime}\>:\>\mathcal{D}^{\prime\prime},\mathcal{P}^{\prime\prime}}$
Figure 5: Operational Semantics of GIPL

#####  2.2.2.9 Examples of Lucid Programs

Two simple examples of Lucid programs are presented. The examples demonstrate
absence of iterative/sequential operation as opposed to the traditional
imperative programming languages.

###### Natural Numbers Problem

An example program in Indexical Lucid that yields 44 as the result is in
Figure 6. The way the program is expanded using the re-definitions of the
Lucid operators, such as fby, employing @ and # in GIPL is shown in Figure 7.

    N @.d 2
    where
        dimension d;
        N = 42 fby.d (N + 1);
    end;

Figure 6: Natural numbers problem in Indexical Lucid.

    N @.d 2
    where
        dimension d;
        N = if (#.d <= 0) then 42 else (N + 1) @.d (#.d - 1) fi;
    end;

Figure 7: Natural numbers problem in GIPL.

###### The Hamming Problem

This example (see Figure 8) illustrates the simple use of functions in Lucid.

    H
    where
        H = 1 fby merge(merge(2 * H, 3 * H), 5 * H);

        merge(x, y) = if(xx <= yy) then xx else yy
        where
            xx = x upon(xx <= yy);
            yy = y upon(yy <= xx);
        end;
    end;

Figure 8: Indexical Lucid program implementing the merge() function.

####  2.2.3 Lucid Now

To summarize, Lucid is a functional programming language where a variable
(stream), a function, a dimension, or even entire context can be a first class
value (i.e. can viewed and manipulated as data). Lucid provides operators,
such as @ and #, to navigate within dimensions and switch contexts. The
language also exhibits the eductive execution model (demand-driven distributed
computation) that augments the semantics with a warehouse (intensional value
cache) and its consistency222Paquet defines the augmented operational
semantics in [Paq99] and Tao implements its first incarnation in GIPSY
[Tao04]. This work has an impact on this aspect by introducing the side
effects with the imperative languages, which will be discussed later..

###  2.3 Hybrid Programming

There have been previous approaches to couple intensional or functional and
imperative and object-oriented paradigms prior to this work. Some recent
related work on the same issue is presented in [BM96, PK04, MS01, SM02] with
the [PK04] being the most relevant. The two major approaches of addressing the
OO issue are – either (1) to extend Lucid to become object-oriented or
objects-aware or (2) make a host imperative language be extended to embed
Lucid. The authors of [PK04] chose the latter by extending GLU-with-C to
GLU#-with-C++, whereas this work approaches the problem from Lucid to Java.
This means a Lucid program is the main one driving the computation. We will
briefly consider the following approaches to the hybrid programming:

  * •

ML≤

  * •

FC++

  * •

GLU

  * •

GLU#

####  2.3.1 ML≤

ML≤ [BM96] is a system introduced in 1996 that proposed to marry OOP and
functional paradigms using their own language and providing the details of the
predicative and decidable typing rules and operational semantics of such a
system. Their main goal is to be able to induce implicit polymorphism of
functional languages in objects. They do not extend an existing functional
language with the OO capabilities, instead they reinterpret all data types as
either abstract or concrete classes and use the dynamic dispatch, a typical OO
feature, on run-time types.

####  2.3.2 FC++

FC++ [MS01, SM02] tries to promote the functional paradigm in C++. FC++ is a
library add-on to enable higher-order polymorphic functions in a novel use of
C++ type inference that is not very complex and is still expressive. FC++ adds
support for both parametric and subtype polymorphism policies for functions in
order to be able to fit FC++ functions within the C++ object model and pass
higher-order functions as parameters. The FC++ functions are kept as objects
called functoids and use a reference counter machinery for allocation and de-
allocation. Closures in FC++ (operation on a some state and the state itself)
can automatically be created during functoid object creation, but their
“closing” of that state is not automatic and the state values have to be
passed explicitly during the creation process. The library also adds a set of
functional operators from the Haskell Standard Prelude. FC++ comes more from
the OOP-to-functional point of view and conforms with standard software
engineering design patterns and is suitable for the common OO tasks.

####  2.3.3 GLU

GLU was the most general intensional programming tool recently available
[JD96]. However, experience has shown that, while being very efficient, the
GLU system suffers from a lack of flexibility and adaptability [Paq99]. Given
that Lucid is evolving continually, there is an important need for the
successor to GLU to be able to stand the heat of evolution [Paq99]. The two
major successors of GLU are the GIPSY and GLU# systems.

##### Eduction

The earlier mentioned notion of eduction was first introduced by the GLU
compiler. GLU supports so-called tagged-token demand-driven dataflow where
data elements (tokens) are computed on demand following a dataflow network
defined in Lucid. Data elements flow in the normal flow direction (from
producer to consumer) and demands flow in the reverse order, both being tagged
with their current context of evaluation. This form of lazy computation is
inherited by GIPSY from GLU.

####  2.3.4 GLU#

GLU# [PK04] is a successor of GLU, which enables Lucid within C++. The authors
argue for the embedding small functional/intensional-language pieces of Lucid
into C++ programs allowing lazy (demand-driven) evaluation of arrays and
functions thereby making Lucid easily accessible within a popular imperative
programming language, such as C++. Because GLU# appeared quite recently (2004)
to when this work was written, its success compared to GLU is yet to be
evaluated; however, it seems to suffer from the same inflexibility GLU did and
targets only C++ as a host language.

###  2.4 Compiler Frameworks

A significant number of compiler frameworks emerged for the past decade. All
try to enable compilation of more than one language, either hybrid or not, in
an uniform manner. Some frameworks or libraries became “frozen” (i.e. non-
extendable) and fixed to a specific set of languages, some other ones were
build with the extension in mind, so it is relatively easy to “plug-in” yet
another compiler into the system (a collection of compilers and the necessary
tools) with minimum integration work required. A brief overview of different
compiler frameworks is given next:

  * •

GLU tried to accommodate Fortran, C, and Lucid in one system, but was made so
inflexible [Paq99] that it would take a significant effort to extend it and
add other languages to the system.

  * •

GLU# merges Lucid and C++; however, makes no provisions for extension to other
languages on either intensional or imperative side.

  * •

Microsoft .NET can also be thought of a commercial heterogeneous compiler
framework (it is more than a compiler framework, but our focus is on
compilers) that allows easy cooperation and application development between
different language models, such as C#, C++, Visual Basic, and Assembly in a
homogeneous environment. However, none of these languages have natively any of
the intensional or functional capabilities, so no native debugging support or
other tools exist, even if one starts using FC++ or GLU# in this environment.
Despite the fact that all programs can be compiled into the common bytecode,
the debugging tools have to be aware of the functional paradigms on a higher
level and they are not (at least at this writing).

  * •

The GNU Compiler Collection (GCC) can also be said as a compiler framework
from the free software [CP05]. It supports C, C++, Objective-C, Objective-C++,
Java, Fortran, and Ada. Again, these languages are more of an imperative
nature, but it is far easier to add new language into GCC than to Microsoft
.NET due to its openness.

  * •

Finally, the GIPSY presents the GIPC framework that is designed for expansion
and integration of the intensional and imperative (and later functional)
languages. This is presented through the rest of this thesis.

###  2.5 General Intensional Programming System

####  2.5.1 Introduction

Figure 9: The GIPSY Logo representing the distributed nature of GIPSY.

GIPSY is broadly presented in [WPG03, Lu04, PW05], and others. Please refer to
the online resources [RG05a, PW05, RG05b] to obtain the most current status of
the project. GIPSY is primarily implemented in Java. General GIPSY
architecture is presented in Figure 10. The essence behind GIPSY is demand-
driven computation support for the intensional programming languages, e.g.,
Indexical Lucid, Tensor Lucid [Paq99], etc.

Figure 10: Structure of the GIPSY

The GIPSY consists in three modular sub-systems: the General Intensional
Programming Language Compiler (GIPC); the General Eduction Engine (GEE), and
the Intensional Run-time Interactive Programming Environment (RIPE). The sub-
systems have to be modular so that one implementation of parts of them or the
whole can be replaced by another without having major if any impact on the
other modules. Although the theoretical basis of the language has been
settled, the implementation of an efficient, general and adaptable programming
system for this language raises many questions. The following sections outline
the theoretical basis and architecture of the different components of the
system. All these components are designed in a modular manner to permit the
eventual replacement of each of its components – at compile-time or even at
run-time – to improve the overall efficiency and productivity of the system
[Paq99].

A GIPSY instance sends out little bits of work to others to compute and then
gathers the results in distributed fashion. Of course, synchronization,
latency tolerance, and maximum utilization of resources are primary goals for
the system to be productive. Unlike in most programming language models (see
[ST98]) considered for parallel computation, in GIPSY several key concepts are
considered:

  * •

Thread-Level Parallelism (TLP)

  * •

Stream-Level Parallelism (SLP)

  * •

Cluster-Level Parallelism (CLP)

GIPSY’s parallelism granularity takes into account the amount of TLP, SLP, and
CLP available. TLP determines the maximum number of threads that should or can
be created when a Lucid program is being executed. In other words, TLP defines
on how many pieces of terminal computational work we can chop a big job into.
The goal, as far as programming is concerned, is to program for infinite TLP,
and later adjust (load-balance) at run-time to the actual amount of SLP. SLP
determines the maximum number of streams available to execute the threads.
Here, by “streams” we mean processors but, with the invention of multithreaded
CPUs for a single processor, there may be several thread streams available in
parallel, and hence a more general notion of SLP. The amount of SLP is
machine-dependent and has to be discovered at run-time on remote machines. If
a job is to be run on a single machine, GIPSY tries to maximize SLP
utilization, providing just enough TLP for the machine in question with the
design goal of always assuming infinite TLP. Then load-balancing comes into
play. CLP takes GIPSY to another level — distributed computing, involving
utilization of SLP of the machines across the network nearby or across the
globe over the Internet.

NOTE: the Lucid family of languages has also a notion of streams that refers
to Lucid variables that evaluate in multiple contexts. Every Lucid stream
(e.g. a variable) can potentially be evaluated on any hardware stream
available, but it is important not to confuse the two kinds of streams. The
reason for the existence of the two notions is that both terms were used
independently in each field. Now that parallel architectures and language
models such as Lucid came into proximity, the terms clash.

####  2.5.2 Goals

The system has to withstand the evolution of the tools, languages, and
underlying platforms, thus be flexible and adaptable to the changes. That is
one of the most important and stringent requirements put on the development of
GIPSY [Paq99]. Other subordinate requirements in compiler design, run-time
system, communication, and user interfaces are presented in detail throughout
the follow up sections.

####  2.5.3 General Intensional Programming Compiler

Figure 11: Initial Conceptual Design of the GIPC

GIPSY programs are compiled in a two-stage process (see Figure 19, page 19).
First, the intensional part of the GIPSY program is translated in Java, then
the resulting Java program is compiled in the standard way.

The source code consists of two parts: the Lucid part that defines the
intensional data dependencies between variables and the sequential part that
defines the granular sequential computation units (usually written in any
imperative language, e.g. C or Java). The Lucid part is compiled into an
intensional data dependency structure (IDS) describing the dependencies
between each variable involved in the Lucid part. This structure is
interpreted at run-time by the GEE following the demand propagation mechanism.
Data communication procedures used in a distributed evaluation of the program
are also generated by the GIPC according to the data structures definitions
written in the Lucid part, yielding a set of communication procedures (CP).
These are generated following a given communication layer definition such as
provided by RPC (or rather RMI since GIPSY is implemented in Java), CORBA,
Jini, or the WOS [BKU98]. The sequential functions defined in the second part
of the GIPSY program are translated into imperative code using the second
stage imperative compiler syntax, yielding imperative sequential threads (ST).
Intensional function definitions, including higher order functions, will be
flattened using a well-known efficient technique [Ron94, Paq99]. The closures
in the higher order functions case are still applicable because the function
state and the operation on it are correctly passed to the functions by
expanding and using function definitions inline. The insignificant limitation
here is that self-referential closures for such functions cannot be made. The
function elimination in GIPSY pertinent to some of these aspects was
implemented by Wu in [Wu02].

The Figure 11 presents the initial conceptual design of the GIPC. Based on
this design, the GIPSY module integration and the development of the STs and
CPs support has begun. Later on the design was refined in [PGW04, MP05a] and
its latest reincarnation is shown in Figure 4 in Chapter 4, page 4; thus, the
evolution description is delayed until then.

Prior this work, GIPC supported only two Lucid dialects: GIPL and Indexical
Lucid. The initial GIPC compiler was implemented by Chun Lei Ren in [Ren02],
and the translation of the Indexical Lucid into GIPL and the semantic analysis
was implemented by Aihua Wu in [Wu02]. A large integration and re-engineering
effort went into GIPC to approach it to the goals of the GIPSY (see Section
2.5.2) and add more compilers for investigation of the underlying language
models. The results of this effort are presented in the Design and
Implementation chapter (Chapter 4).

####  2.5.4 General Eduction Engine

Figure 12: Conceptual Design of the GEE

The GIPSY uses a demand-driven model of computation, which is based on the
principle is that certain computation takes effect only if there is an
explicit demand for it. The GIPSY uses eduction, which is demand-driven
computation in conjunction with an intelligent value cache called a warehouse.
Every demand can potentially generate a procedure call, which is either
computed locally or remotely, thus eventually in parallel with other procedure
calls. Every computed value is placed in the warehouse, and every demand for
an already-computed value is extracted from the warehouse rather than computed
again and again (demands that may have side effects, e.g. if we cache results
of STs, shall not be cached). Eduction, thus, reduces the overhead induced by
the procedure calls needed for the computation of demands sequentially. Figure
12 describes the internal conceptual structure and functioning of the GEE.

The GEE itself is composed of three main modules: the executor, the
intensional demand propagator (IDP), and the intensional value warehouse
(IVW). First, the intensional data dependency structure (IDS, which represents
GEER) is fed to the demand generator (DG) by the compiler (GIPC). This data
structure represents the data dependencies between all the variables in the
Lucid part of the GIPSY program. This tells us in what order all demands are
to be generated to compute values from this program. The demand generator
receives the initial demand, that in turn raises the need for other demands to
be generated and computed as the execution progresses. For all non-functional
demands (i.e. demands not associated with the execution of sequential threads
(ST)), the DG makes a request to the warehouse to see if this demand has
already been computed. If so, the previously computed value is extracted from
the warehouse. If not, the demand is propagated further, until the original
demand resolves to a value and is put in the warehouse for further use. This
type of warehousing was introduced by GLU due to its distributed nature to cut
down on communication costs, but it can certainly be applicable to any
functional language, such as LISP, Scheme, Haskell, ML and others to improve
efficiency even on a single machine provided there are no any side effects
whatsoever. The garbage collector can run on the background to clean up old
function-parameters-values tuples periodically, and given that the large
amounts of memory are cheap these days functional languages may gain much more
popularity with the increased performance.

For functional demands (i.e. demands associated with the execution of a
sequential thread), the demands are sent to the demand dispatcher (DD) that
takes care of sending the demand to one of the workers or to resolve it
locally (which normally means that a worker instance is running on the
processor running the generator process). If the demands are sent to a remote
worker, the communication procedures (CP) generated by the compiler are used
to communicate the demand to the worker. The demand dispatcher (DD) receives
some information about the liveness and efficiency of all workers from the
demand monitor (DM), to help it make better decisions in dispatching the
demands.

The demand monitor, after some functional demands are sent to workers, starts
to gather various types of information about each worker, including, but not
limited to:

  * •

liveness status (is it still alive, not responding, or dead)

  * •

network link performance

  * •

response time statistics for all demands sent to it

These data points are accessed by the DD to make better decisions about the
load balancing of the workers, and thus achieving better overall run-time
efficiency.

Bo Lu was the first one to do the original design of the GEE framework [Lu04]
and investigate its performance under threaded and RMI environments. She also
introduced the notion of the Identifier Context (IC) classes – demands
converted into Java code and using Java Reflection [Gre05] to compile, load,
and execute them them at run-time. She also contributed the first version of
the interpreter-based execution engine. Next, Lei Tao contributed the first
incarnation of the intensional value warehouse and garbage collection
mechanisms in [Tao04] based on the popular scientific library called NetCDF.
The author of this thesis put an effort to modularize these all and make them
easier to extend and customize. He also provided the initial GEE application
to start available network services. The GEE was also made aware of the STs
and CPs as well as the new type system, described in Section 4.1.1.5. Further,
Emil Vassev [VP05] produced a very general and functional framework for demand
migration and its implementation, Demand Migration System (DMS) that supports
among other things Jini, CORBA, and .NET Remoting for fault-tolerant demand
transportation system, a part of the Demand Dispatcher. The DMS is still
pending integration as of this writing.

#####  2.5.4.1 Demand Propagation Resources for the GEE

The IDP generates and propagates demands according to the data dependence
structure (DPR, now renamed to GEER in [WPG03]) generated by the GIPC. If a
demand requires some computation, the result can be calculated either locally
or on a remote computing unit. In the latter case, the communication
procedures (CP) generated by the GIPC are used by the GEE to send the demand
to the worker. When a demand is made, it is placed in a demand queue, to be
removed only when the demand has been successfully computed. This way of
working provides a highly fault-tolerant system. One of the weaknesses of GLU
is its inability to optimize the overhead induced by demand-propagation. The
IDP will remedy to this weakness by implementing various optimization
techniques:

  * •

Data blocking techniques used to aggregate similar demands at run time, which
will also be used at compile-time in the GIPC for automatic granularization of
data and functions for data-parallel applications

  * •

The performance-critical parts (IDP and IVW) are designed as replaceable
modules to enable run-time replacements by more efficient versions adapted to
specific computation-intensive applications

  * •

Certain demand paths identified (at compile-time or run-time) as critical will
be compiled to reduce their demand propagation overhead

  * •

Extensive compile-time and run-time rank analysis (analysis of the
dimensionality of variables) [Dod96].

#####  2.5.4.2 Synchronization

##### Distributed vs. Parallel

It is important to make a distinction between parallel and distributed
computing. In parallel computing, SLP matters and latency tolerance for memory
references with mostly UMA (uniform memory access) characteristics, whereas in
distributed computing communication is much more expensive (and perhaps even
prohibitive) and CLP matters as well. This setup largely exhibits NUMA (non-
UMA) characteristics (see [Pro03b]) and latency tolerance (and so also fault
tolerance) has a higher significance. This greatly impacts the way we
synchronize in parallel and distributed worlds.

###### Synchronization in Distributed Environment

A distributed environment is a very popular domain these days, so we’ll start
with it first. Typically, the network is the scarce resource and is the
bottleneck for a distributed application because it implies communication
(e.g., MPI), which is often unacceptable. Therefore, many distributed
applications choose not to communicate at all or communicate very little
through message passing. This implies blocking on waiting for the network
requests to propagate, i.e. network latency.

###### Synchronization in Parallel Environment

Synchronization in a parallel environment is more fine-grained, often at the
hardware level (e.g., a full/empty bit in memory cells). Java does not give us
control over such synchronization, so we have to rely on the JVM built for an
architecture that has such synchronization. The JVM has to be developed to
make use of the full/empty bits that are usually represented as future
variables [Pro03b, JA03] in the languages specifically designed for parallel
computing.

##### Secure Synchronization

Secure synchronization is especially pertinent in a distributed environment.
Like any act of communication within worker-generator architecture (see
Section 3.3.3.4) and a warehouse (Figure 19; Section 2.5.4.1), synchronization
has to be secure to avoid (a) over-demanding, (b) incorrect results sent back,
(c) loss of results and demands, and (d) poisoning the warehouse with wrong
data. Secure synchronization implies fault tolerance. In GIPSY, we will rely
on Java’s RMI and Jini over JSSE for secure communication in a distributed
environment, using Java’s synchronization primitives (see Section 2.5.4) to
achieve the goal of secure synchronization. Thus, the reliability and
accountability of the results of a GIPSY program are dependent on these
properties of underlying Java Runtime Environment (JRE) and the communication
protocols used.

##### Implicit vs. Explicit Synchronization

One of the productivity metrics of a software completing its task on time, is
the efficiency of development of (see [Pro03c]) such a software, i.e., the
amount of programmer’s effort required to create and debug the software. This
is essentially a metric, called time-to-solution (TTS) [Pro03c]; from creation
until the end result (e.g. completion of some scientific computation). The
goal is to minimize TTS. One way to achieve this is ease of programming. As
the proportion of the work done by the compiler increases, so does the
reliability of the code, but we target scientific researchers, not just
programmers. Scientific researchers from math and physics should not care
about these issues and, thus, just be concerned mastering the basics of Lucid.
Therefore, the programmer has to be freed from taking care of synchronization
explicitly, which a source of bugs and inefficiency of programming (e.g.,
using Java’s synchronization primitives, such as synchronized, Object.wait(),
Object.notify(), and Object.notifyAll(), [Fla97]). The programmer should
rather focus on the problem being solved and let the compiler/run-time system
deal with the synchronization pain. The GIPSY system, built around the Lucid
family, advocates implicit synchronization either by wrapping around the
Java’s synchronization primitives or through the communication synchronization
and data dependencies (although a complete discussion is beyond the scope of
this thesis, see [Lu04, VP05]).

####  2.5.5 Run-time Interactive Programming Environment

Figure 13: Conceptual Design of the RIPE

The RIPE is a visual programming aid to the run-time environment (GEE)
enabling the visualization of a dataflow diagram corresponding to the Lucid
part of the GIPSY program, source code editing, launching the compilation and
execution of GIPSY programs. The original conceptual design of RIPE [Paq99] is
illustrated in Figure 13. The user’s points of interaction with the RIPE at
run-time vary in the following ways:

  * •

Enable interactive editing of GIPSY programs via a variety of editors
(textual, graphical, web).

  * •

Dynamic inspection of the IVW.

  * •

Modification of the input/output channels of the program.

  * •

Recompilation of the GIPSY programs.

  * •

Modification of the communication protocols.

  * •

Swapping of the parts of the GIPSY itself (e.g. garbage collection,
optimization, warehouse caching etc. strategies).

Because of the interactive nature of the RIPE, the GIPC is modularly designed
to allow the individual on-the-fly compilation of either the IDS (by changing
the Lucid code), CP (by changing the communication protocol), or ST (by
changing the sequential code). Such a modular design even allows sequential
threads to be programs written in different languages (for now, we are
concentrating on Java sequential threads, but a provision is made for easy
inclusion of other languages with the GICF, Section 4.1.1.1).

The RIPE even enables the graphic development of Lucid programs, translating
the graphic version of the program into a textual version that can then be
compiled into an operational version through a DFG generator of Yimin Ding
[Din04]. However, the development of this facility for graphical programming
posed many problems whose solution is not yet settled, for example
representation of the STs and CPs in the DFG nodes. An extensive and general
requirements analysis will be undertaken, as this interface will have to be
suited to many different types of applications. There is also the possibility
to have a kernel run-time interface on top of which we can plug-in different
types of interfaces adapted to different applications, such as stand-alone,
web-, or server-based.

###  2.6 Tools

This section presents a brief description of a variety of tools that helped
most with the implementation aspects of this work.

####  2.6.1 Java as a Programming Language

The primary implementation language of GIPSY is Java. This includes using
Java’s Reflection, JNI, and JUnit frameworks and packages. We have chosen to
implement our project using the Java programming language mainly because of
the binary portability of the Java applications as well as its facilities, for
e.g. memory management and communication tasks, so we can concentrate more on
the algorithms instead. Java also provides built-in types and data-structures
to manage collections (build, sort, store/retrieve) efficiently [Fla97,
Mic05b]. There is also source code written in other languages in the main
GIPSY repository. This includes LEFTY code for DFG generation and the code of
the test intensional programs in various Lucid dialects. The Java versions
supported by GIPSY are 1.4 and 1.5. The GIPSY will no longer build on 1.3 and
earlier JDKs.

#####  2.6.1.1 Java Reflection

Java Reflection Framework java.reflect.* [Gre05] allows us to
load/query/discover a given class for all of its API through enumeration of
constructors, fields, methods, etc. at run-time. This is incredibly useful for
dynamic loading and execution of our compilers, identifier context classes,
and sequential threads on local and remote machines.

The basic API from the reflection framework used in the implementation of
GIPSY is the Class class that allows getting arrays of declared Method objects
through the getDeclaredMethods() call that will become the STs at the end,
then for each Method the reflection API allows getting parameter and return
types via getParameterTypes() and getReturnType() calls, which will become the
CPs. The Class.newInstance() method allows instantiating an object off the
newly generated class. Likewise, an enumeration of Constructor objects is
acquired through the Class.getConstructors() call. Constructors in Java are
treated differently from methods because they are not inherited and don’t have
a return type (except that the type of the object they create). We still need
to enumerate them to allow Objective Lucid programs to use the constructors,
default or non-default, directly, so we can get a handle on them similarly to
STs.

#####  2.6.1.2 Java Native Interface (JNI)

The Java Native Interface (JNI) [Ste05] is very useful for the thread
generation component of the GIPC. We rely on JNI to increase the number of
popular imperative languages in which the sequential threads could be written.
Developers use the JNI to handle some specific situations when an application
cannot be written entirely in Java, e.g. when the standard Java classes do not
provide some platform-dependent features an application may require, or use a
library written in another language be accessible to Java applications, or for
performance reasons a small portion of a time-critical code has to be written
say in C or assembly, but still be accessible from a Java application [Ste05].
In GIPSY, the second and third of the listed cases are most applicable (e.g.
to adopt GLU programs). The JNI will allow us to avoid Lucid-to-C or Lucid-
to-C++ type matching as we can do it all through Java and maintain only Lucid-
to-Java type mapping table.

The JNI is made so that the native and Java sides of an application can pass
back and forth objects, strings, arrays and update their state on either end
[Ste05]. The JNI is bi-directional, i.e., allows Java to use the native
libraries and applications and provide access to Java libraries from the
native applications.

The general methodology of creating a JNI application say that interacts with
a C implementation is done in six steps [Ste05]:

  1. 1.

Write a Java code with a native method to be implemented in C, the main(), and
the dynamic loading statement for a library (to be compiled in the next
steps).

  2. 2.

Compile the Java code with javac and produce a .class file.

  3. 3.

Create a C header .h file from the compiled .class file by calling javah. This
header file will provide the necessary #include directives along with the
C-style prototype declaration of the native method.

  4. 4.

Next, write the implementation of the function in regular C in a .c file.

  5. 5.

Then, create a shared library by compiling the .h and .c files with a C
compiler.

  6. 6.

Run the application regularly with the JVM (java).

#####  2.6.1.3 JUnit

JUnit is an open-source Java testing framework used to write and run automated
repeatable unit tests in a hassle-free manner [GB04]. The goal is to sustain
application correctness over time, especially when undergoing a lot of
integration efforts. JUnit is designed with software architecture patterns in
mind and follows best software engineering practices. It encourages developers
to write tests for their applications that withstand time and bit rot.

The main abstract class is TestCase that follows the Command design pattern
that implements the Test interface. This class maintains the name of the tests
(if it fails) and defines the run() method that has to be overridden to do the
actual testing work. The default Template Method run() simply does three
things: setUp(), runTest(), and tearDown(). Their default implementation is to
do nothing, so a developer can override them as necessary. Then, to collect
the test results they apply Collecting Parameter pattern. They use the
TestResult class for that.

JUnit makes a distinction between errors and failures in the following way:
errors to JUnit are mostly unexpected run-time or regular exceptions, whereas
failures are anticipated and are tested for using assertion checks. The errors
and failures are collected for further test failure reporting.

To run tests in a general manner from the point of view of the tester, the
test classes have with a generic interface using the Adapter pattern. JUnit
also offers a pluggable selector capability via the Java Reflection API
[Gre05]. The TestSuite class represents a collection of tests to run. In the
GIPSY, the Regression application (see Section 5.1) comprises concrete
implementation of such a test suite that tests most of the feasible
functionality of the GIPC and GEE modules. See more details of application of
JUnit to the GIPSY in Chapter 5.

####  2.6.2 javacc – Java Compiler Compiler

JavaCC [VC05], accompanied by JJTree, is the tool the GIPSY project is relying
on since the first implementation [Ren02] to create Java-language parsers and
ASTs off a source grammar files. The Java Compiler Compiler tool implements
the same idea for Java, as do lex/yacc [Lou97] (or flex/bison) for C – reading
a source grammar they produce a parser that complies with this grammar and
gives you a handle on the root of the abstract syntax tree. The GIPL,
Indexical Lucid, JLucid, Objective Lucid, PreprocessorParser, and DFGGenerator
parsers are generated with the JavaCC/JJTree parser generation tools. JavaCC
is a LL(K) [Lou97] parser generator, so the original GIPL and Indexical Lucid
grammars and the new grammars had to be modified to eliminate or avoid the
left recursion.

####  2.6.3 MARF

Modular Audio Recognition Framework (MARF) library [MCSN05] provides a few
useful utility and storage classes GIPSY is using to manipulate threads,
arrays, option processing, and byte operations. Despite MARF’s belonging to a
voice/speech/natural language recognition and processing library, it contains
a variety of useful utility modules for threading and options processing.

####  2.6.4 CVS

For managing the source code repository the Concurrent Versions System (CVS)
[BddzzP+05] is used. The CVS allows multiple developers work on the up-to-date
source tree in parallel that keeps tracks of the revision history and works in
an transactional manner. The author produced a mini-tutorial on the CVS
[Mok03a] for the GIPSY Research and Development team, which contains the
necessary summary for the team to work with the project repository.

While CVS has a comprehensive set of commands, the basic set includes:

  * •

init to initialize the repository

  * •

checkout or co to checkout the source code tree from the repository to a local
directory

  * •

update or up to make the local tree up-to-date with the one on the server

  * •

add to schedule a new file inside the existing local checkout for addition to
the repository

  * •

remove to schedule a new file inside the existing local checkout for removal
from the repository

  * •

commit to upload the changes done locally to the server

  * •

diff to show the differences between the local and the server versions of the
tree

####  2.6.5 Tomcat

Apache Jakarta Tomcat [Fou05] is an open-source Java application servlet and
server pages container project from Apache Foundation to run web Java-based
applications written in accordance with the Java Servlet and JavaServer Pages
[Mic05a, Mic05c] specifications developed by Sun Microsystems. Tomcat powers
up the web front end to GIPSY to test intensional programs online. The web
frontend is represented by the WebEditor servlet as of this writing a part of
RIPE which is discussed later in Chapter 4. Tomcat has an easy interface to
deploy Java-based applications and their libraries, e.g. through a manager
presented in Figure 14.

Figure 14: Tomcat Web Applications Manager

Tomcat itself consists from a variety of modules that includes implementation
of the JSP (Jasper engine) and Servlet APIs, a webserver called Coyote, the
application server called Catalina, and many other things for logging,
security, administration, etc.

####  2.6.6 Build System

The GIPSY’s sources can be built using a variety of ways, using different
compilers and IDEs on different platforms. This includes Linux Makefiles,
IBM’s Eclipse, Borland’s JBuilder, Apache’s Ant, and Sun’s NetBeans.

#####  2.6.6.1 Makefiles

Unix/Linux Makefiles are targeting all Unix systems that support GNU make
(a.k.a gmake) [SMSP00, Mok05a]. Often, to compile all of the GIPSY is just
enough to type in make and the system will be built. All Unix versions support
make, and our system has been tested to build on Red Hat Linux 9, Fedora Core
2, Mac OS X, and Solaris 9. There is a test script make-test.sh that tests
whether we are dealing with the GNU make on Unix systems, as this is the only
make supported.

#####  2.6.6.2 Eclipse

There are project files .project and .classpath that belong to this IDE from
IBM [c+04]. The GIPSY build with this IDE properly and has its library
CLASSPATH set. Eclipse is another open source tool available free of charge
and provides extended tools for Java projects development, refactoring, and
deployment.

#####  2.6.6.3 JBuilder

There is a project file GIPSY.jpx that belongs to this IDE from Borland
[Bor03]. The GIPSY build with this IDE properly and has its library CLASSPATH
set.

#####  2.6.6.4 Ant

There is a project file build.xml that belongs to this build tool from the
Apache Foundation [Con05]. The GIPSY build with this tool properly and has its
library CLASSPATH set. In this case build.xml is a portable way to write a
Makefile in XML.

#####  2.6.6.5 NetBeans

There is a project file nbproject.xml that belongs to this IDE from Sun
[Mic04]. The GIPSY build with this IDE properly and has its library CLASSPATH
set.

####  2.6.7 readmedir

This script generates a human-readable description of a directory structure
starting from some directory with file listing and possibly descriptions (for
this there should be specially formatted file README.dir in every directory
traversed. The contents of this file will be a part of the output and is a
responsibility of the directory creator/maintainer. The output formats of the
script are LaTeX, HTML, and plain text.

###  2.7 Summary

In this chapter the reader was introduced to the necessary background on the
GIPSY project and how it is being managed starting from the Lucid language
origins to its implementations in the GIPSY and the summary of the tools used
to aid the advancement of the project. In the GIPSY section the three main
modules were introduced, such as GIPC, GEE, and RIPE. While most of the
remaining work has gone into the GIPC in this thesis, the author had to
perform the necessary integration and adjustments to the GEE and RIPE.

##  Chapter 3 Methodology

This chapter focuses on the methods and techniques proposed to the solve the
stated problems (see Section 1.1). The approaches described are based on three
publications, namely [MPG05, MP05b, MP05a]. Section 3.1 introduces the JLucid
language and all related considerations including the syntax and semantics.
Next, Objective Lucid is introduced along with its syntax and semantics.
Further, the GICF is introduced by providing the necessary requirements for it
to exist and the way to satisfy them. Lastly, the summary is presented
outlining the benefits and limitations of the proposed solutions.

###  3.1 JLucid: Lucid with Embedded Java Methods

####  3.1.1 Rationale

The name JLucid comes from the GIPC component known as Java Compiler within
the Sequential Thread (ST) Generator of the GIPSY. It subsumes all of
Indexical Lucid and General Intensional Programming Language (GIPL) [Paq99]
and syntactically allows embedded Java code. In fact, a JLucid program looks
like a partial fusion of the intensional and Java code segments. JLucid gives
a great deal of flexibility to Lucid programs by allowing to use existing
implementations of certain functions in Java, providing I/O facilities and
math routines (that Lucid entirely lacks), and other Java features accessible
to Lucid, arrays, and permits to increase the granularity of computations at
the operator level by allowing the user to define Java operators, i.e.,
functions manipulating objects, thus allowing streams of objects111A more
precise meaning of Java objects within Lucid is explored further in the
Objective Lucid language, including the meaning of an object stream and how
object members are manipulated (see for example Section 3.2 and Section
4.1.3.6). Additionally, since the actual Java objects are flattened into
primitive types, it would be possible to access object members in parallel
manner. in Lucid. JLucid more or less achieves the same goals and mechanisms
as provided by GLU. What we are proposing is a flexible compiler and run-time
system that permits the evolution of languages through a framework approach
[MP05a, PW05].

#####  3.1.1.1 Modeling Non-Determinism

Lucid, by its nature, is deterministic, so introduction of imperative
languages, such as Java, may allow us to model non-determinism in Lucid
programs for example by providing access to random number generators available
to the imperative languages. Non-determinism can also be introduced as a
result of side effects from for example reading a different file each time an
ST is invoked, or making a database query against a table where data regularly
changes, or say by reading the current time of day value. Of course, a special
care should be taken not to cache the results of such STs in the warehouse.

#####  3.1.1.2 Loading Existing Java Code with embed()

In a nutshell, we want to make the following possible for the Indexical Lucid
program in Figure 1 (replicated here from Chapter 2 for convenience) to become
something as in Figure 2 or, alternatively as in Figure 3. The latter form
would allow us to include objects from any types of URLs, local, HTTP, FTP,
etc. The idea behind embed() is to include or to import the code written
already by someone and not to rewrite it in Lucid (which may not be a trivial
task). It is not meant to adjust to URL’s existence at run-time as all embed-
referenced resources are resolved at compile time. We “include” the pointed-to
resource and attempt to compile it where the original program-initiator
resides. If the URL is invalid at compile time, then there will be a compile
error and no computation will be started. embed() by itself does not
necessarily provoke a remote function call.

    H
    where
        H = 1 fby merge(merge(2 * H, 3 * H), 5 * H);

        merge(x, y) = if(xx <= yy) then xx else yy
        where
            xx = x upon(xx <= yy);
            yy = y upon(yy <= xx);
        end;
    end;

Figure 1: Indexical Lucid program implementing the merge() function.

    #JAVA

    void merge(int x, int y)
    {
        // java code here
    }

    #JLUCID

    H
    where
        H = 1 fby merge(merge(2 * H, 3 * H), 5 * H);
    end;

Figure 2: Indexical Lucid program implementing the merge() function as inline
Java method.

    H
    where
        H = 1 fby merge(merge(2 * H, 3 * H), 5 * H);
        merge(x, y) =
            embed("file://path/to/class/Merge.class", "merge", x, y);
    end;

Figure 3: Indexical Lucid program implementing the merge() function as
embed().

    F
    where
        dimension d;
        F = foo(#d);
        where
            foo(i) = embed("file://my/classes/Foo.class", "foo", i);
        end;
    end;

Figure 4: Illustration of the embed() syntax.

Existing Java code, in either .class or .java form, can be loaded with
embed(). Intuitively, we would prefer the approach presented in Figure 4. That
added flexibility requires syntactical extension of Lucid and is not portable.
For the program in Figure 4 to work, foo() has to return a Java type of int,
byte, long, char, String, or boolean, as per Table 1, page 1. A wrapper class
will be created to extend from the Foo and implement the ISequentialThread
interface (see Appendix B.1). General embed() syntax would be defined as
follows:

id(id, id, ...) ::= embed(URI, METHOD, id, id, ...);

where id is the Lucid function name being defined that is mapped to a Java’s
method named METHOD (which may or may not be of the same name as the first
id). The URI is pointing to either .class or .java file. Example URI’s would
be:

foo(a,b) = embed("file://files/Foo.java","bar",a,b); bar(a,b) =
embed("http://www.java.com/Foo.class","foo",a,b); baz(a,b) =
embed("ftp://ftp.file.com/pub/Foo.java","zee",a,b);

These declarations associate Lucid functions with Java implementations. Name
clashes may be avoided, if necessary, by using different function names.
Above, for example, Lucid baz() is implemented by Java zee().

    public class <filename>_<machine_name>_<timestamp>
    extends my.classes.Foo
    implements ISequentialThread
    {
        // The definition is provided later in the text
    }

Figure 5: Generated corresponding ST to that of Figure 4.

There are several ways of making this work. We could extract either a textual
or a bytecode definition of foo(), wrap it in our own class and, (re)compile
it. However, there is an issue here. What about other functions it may use,
like shown in Figure 9 with two methods calling each other? That would mean
extracting those dependencies as well along with the method of interest. This
won’t scale very efficiently. Thus, alternate approaches include: to either
inherit from the desired class as in Figure 5, encapsulate this class
instance, or attempt to wrap the entire class as done for the JAVA segment in
Section 3.1.1.3 below. The former approach would imply having a class variable
instance of the type of that class encapsulated into the wrapper. The latter
approach was chosen as more feasible to implement, although it doesn’t deal
with user-defined classes and subclass and packages the .class or .java file
may require at the moment. Thus, the embed() acts in a way similar to #include
in C/C++ or import in Java of a set of Java definitions to be used in a JLucid
program. Therefore, embed() has to be resolved at compile time. Similar
technique may be taken towards other languages than Java at a later time.
Lucid’s syntax has to be extended to support embed().

#####  3.1.1.3 The #JAVA and #JLUCID Code Segments

This section explores ways of mixing Java and Lucid source code segments in a
single text file and ways of dealing with such a merge.

    F
    where
        dimension d;
        F = foo(#d);
        where
            foo(i) = int foo(int i) { return i + 1; }
        end;
    end;

Figure 6: Inline Java function declaration.

An attempt to use Java’s methods inline, such as in Figure 6 would be
intuitive, but does not justify the effort spent on syntax analysis.
Therefore, we take the inline definition out of the Lucid part, and make it a
separate outer definition of the same method. Additionally, we explicitly mark
the JLUCID and JAVA code segments to simplify pre-processing of the JLucid
code as presented in Figure 7.

    #JAVA

    int foo(int i)
    {
        // Some i + PI
        return (int)(java.lang.Math.PI + i);
    }

    #JLUCID

    F
    where
        dimension d;
        F = foo(#d);
    end;

Figure 7: Java method declaration split out from the Lucid part.

Given the Natural Numbers Problem (see [Paq99]) in Figure 8 (replicated here
for convenience), one could imagine the function definition for $N$ to be
implemented in Java in two functions. To illustrate the point when two
separate functions can call each other in the JAVA segment or several JAVA
segments. This modified JLucid code along with line numbers is shown in Figure
9. Since we allow one Java method to call another within, we have to wrap them
both into the same class.

    N @.d 2
    where
        dimension d;
        N = if (#.d <= 0) then 42 else (N + 1) @.d (#.d - 1) fi;
    end;

Figure 8: Natural numbers problem in plain GIPL.

The JLucid code segments after “#JAVA” constructs will be grouped together by
the compiler. For all definitions (functions, classes, variables) in these
segments, their original location in the JLucid source recorded and statically
put in the wrapper class. These definitions will end up in that wrapper class
as well.

It would be possible to have a class defined within a wrapper class or any
other valid Java declaration; even a data member can be included. To
summarize, the Java segments in the JLucid code are a body of a generated
class that implements the ISequentialThread interface.

         1    #JAVA
         2
         3    int getN(int piDimension)
         4    {
         5        if(piDimension <= 0)
         6            return get42();
         7        else
         8            return getN(piDimension - 1) + 1;
         9    }
        10
        11    int get42()
        12    {
        13        return 42;
        14    }
        15
        16    #JLUCID
        17
        18    N @d 2
        19    where
        20        dimension d;
        21        N = getN(#d);
        22    end;

Figure 9: Natural numbers problem with two Java methods calling each other.

For the example in Figure 9 the parser would proceed as follows:

  * •

In the preprocessing step the source code is split into two parts: the Java
part and the Lucid part. For both parts original source’s line numbers and
length of the definitions are recorded.

  * •

Then they both are fed to the respective parsers. Java’s part requires extra
handling: the Java methods (one or more) defined in the code, have to be
wrapped into a class and then JavaCompiler class that takes the Java portion
of the source and feeds it to javac for syntactic and semantic analyses and
byte code generation. They will become parts of a Sequential Thread, ST (see
Section 3.3.3.1) definition fed to Workers (see Section 3.3.3.4).

  * •

The Lucid part is processed by the modified Lucid compiler (to include the
syntactical modifications for arrays and embed()) and comes up with the main
AST from that.

  * •

The Java STs are then linked into the main AST in place of nodes where the
identifiers of these appear in the Lucid part of the program prior semantic
analysis.

Any method or other definition in the JAVA segment is wrapped into a class.
The generated wrapper class will contain a Hashtable that maps method
signature strings to their starting line in the original JLucid code plus the
length of the definitions in lines of text they occupy statically generated
and initialized. This is needed for the error reporting subsystem in case of
syntax/semantic errors, report back correctly the line in the original JLucid
program and not in the generated class. The class name is created
automatically from the original program name, the machine name it’s being
compiled on, and a timestamp to guarantee enough uniqueness to the generated
class’ name to minimize conflict for multiple such generated classes. Thus,
the JAVA segment in Figure 9 will transform into the generated class as in
Figure 10. This is a short version; for more detailed one please refer to the
Section B.3. In fact, after generating this class (and possibly compiling it)
this situation can be viewed as a special case for embed(), Section 3.1.1.2 or
vice versa. Note, since we have no guarantee the Java methods are side-effects
free in JLucid, their results are not cached in the warehouse.

    public class <filename>_<machine_name>_<timestamp>
    implements gipsy.interfaces.ISequentialThread {
        private OriginalSourceCodeInfo oOriginalSourceCodeInfo;

        // Inner class with original source code information
        public class OriginalSourceCodeInfo {
            // For debugging / monitoring; generated statically
            private String strOriginalSource = ...

            // Mapping to original source code position for error reporting
            private Hashtable oLineNumbers = new Hashtable();

            // Body is filled in by the preprocessor statically
            public OriginalSourceCodeInfo() {
                Vector int_getN_int_piDimension = new Vector();
                // Start line and Length in lines
                int_getN_int_piDimension.add(new Integer(3));
                int_getN_int_piDimension.add(new Integer(7));
                oLineNumbers.put("int getN(int piDimension)",
                                 int_getN_int_piDimension);
                Vector int_get42 = new Vector();
                int_get42.add(new Integer(11));
                int_get42.add(new Integer(4));
                oLineNumbers.put("int get42()", int_get42);
            }
        }

        // Constructor
        public <filename>_<machine_name>_<timestamp>() {
            oOriginalSourceCodeInfo = new OriginalSourceCodeInfo();
        }
        /*
         * Implementation of the SequentialThread interface
         */
        // Body generated by the compiler
        public void run() {
            Payload oPayload = new Payload();
            oPayload.add("d", new Integer(42));

            work(oPayload);
        }

        // Body generated by the compiler statically
        public WorkResult work(Payload poPayload) {
            WorkResult oWorkresult = new WorkResult();
            oWorkresult.add(getN(poPayload.getVaueOf("d")));
            return oWorkResult;
        }

        /*
         * The below are generated off the source file nat2java.ipl
         */
        public static int getN(int piDimension) {
            if(piDimension <= 0) return get42();
            else return getN(piDimension - 1) + 1;
        }

        public static int get42() {
            return 42;
        }
    }

Figure 10: Generated Sequential Thread Class.

In [MPG05] we required foo() in the previous examples to be static. In fact,
any method or other definition in the JAVA segment were to be transformed to
become static while being wrapped into a class. For example, “int foo()
{return 1;}” would become “public static int foo() {...}”. We insisted on
static declarations only because the sequential threads were not instantiated
by the workers when executed. This restriction has been lifted during
implementation as we instantiate and serialize the sequential thread class as
needed.

#####  3.1.1.4 Is JLucid an Intensional Language?

We treat JLucid as a separate specific intensional programming language (SIPL)
rather than a part of a GIPSY program within existing Indexical Lucid
implementation. Here are some pros and cons of this approach and JLucid as a
separate SIPL approach is the winner. Why extend it as a separate SIPL?

  * •

This would serve as an example on how to add other SIPLs.

  * •

This would allow us to keep the original Indexical Lucid clean and working.

  * •

This would allow functions with Java syntax to be used within a Lucid program
as well as binary Java function calls of pre-compiled classes.

  * •

It can be extended to other languages as it turns out to be a successful
approach.

Why not to treat is as a separate SIPL?

  * •

We might want to have embedded Java (or other language) in any intensional
language, not just Indexical Lucid. How to make that possible?

  * •

It is not truly an SIPL, but a hybrid.

####  3.1.2 Syntax

In JLucid, we extend the syntax of both GIPL and Indexical Lucid to support
arrays. For example, it is useful to be able to evaluate several array
elements under the same context. This is included by the last $E$ rules of
$E[E,...,E]$ and $[E,...,E]$ in both syntaxes. Arrays are useful to manipulate
a collection Lucid streams under the same context. JLucid arrays are mapped to
Java arrays on the element-by-element basis with the appropriate element type
matching and may only correspond to arrays of primitive types in Java. The
syntax also includes the embed() extension to allow including external Java
code. The JLucid syntax extensions to GIPL and Indexical Lucid are presented
in Figure 11 and Figure 12.

                        E  ::=   id
                            |    E(E,...,E)
                            |    if E then E else E fi
                            |    # E
                            |    E @ E
                            |    E where Q end;
                            |    [E:E,...,E:E]
                            |    embed(URI, METHOD, E, E, ...)
                            |    E[E,...,E]
                            |    [E,...,E]
                        Q  ::=   dimension id,...,id;
                            |    id = E;
                            |    id(id,...,id) = E;
                            |    QQ

Figure 11: JLucid Extension to GIPL Syntax

                    E      ::=   id
                            |    E(E,...,E)
                            |    if E then E else E fi
                            |    # E
                            |    E @ E E
                            |    E where Q end;
                            |    E bin-op E
                            |    un-op E
                            |    embed(URI, METHOD, E, E, ...)
                            |    E[E,...,E]
                            |    [E,...,E]
                    Q      ::=   dimension id,...,id;
                            |    id = E;
                            |    id.id,...,id(id,...,id) = E;
                            |    QQ
                    bin-op ::= fby | upon | asa | wvr
                    un-op  ::= first | next | prev

Figure 12: JLucid Extension to Indexical Lucid Syntax

####  3.1.3 Semantics

The JLucid extension to the operational semantics of Lucid (see Section
2.2.2.8 on page 2.2.2.8) is defined in Figure 13. As in the original Lucid
semantics, each type of identifier can only be used in the appropriate
situations. Notation:

  * •

freefun, ffid, ffdef mean a type of identifier is a hybrid free (i.e. object-
free) function freefun, where ffid is its identifier and ffdef is its
definition (body).

  * •

The ${\mathbf{E_{ffid}}}$ rule defines JLucid’s free functions.

  * •

The JLucid $\mathbf{\\#JAVA_{ffid}}$ rule add free function definition to the
definition environment.

$\displaystyle{\mathbf{E_{ffid}}}$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!:\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\frac{\begin{array}[]{c}\mathcal{D},\mathcal{P}\vdash
E:id\qquad\mathcal{D},\mathcal{P}\vdash
E_{1},\ldots,E_{n}:v_{1},\ldots,v_{n}\\\ \mathcal{D}(id)=({\texttt{freefun,
ffid, {{\text@underline{ffdef}}}}})\\\
\mathcal{D},\mathcal{P}\vdash<\\!\\!{\mathtt{ffid}}(v_{1},\dots,v_{n})\\!\\!>:v\end{array}}{\mathcal{D},\mathcal{P}\vdash
E(E_{1},\ldots,E_{n}):v}$ $\displaystyle{\mathbf{\\#JAVA_{ffid}}}$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!:\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\frac{{{\mathtt{\underline{ffdef}}}}=\mathit{frttype}\texttt{
ffid}(\mathit{fargtype_{1}}\;farg_{id_{1}},\dots,\mathit{fargtype_{n}}\;farg_{id_{n}})}{\mathcal{D},\mathcal{P}\vdash{{\mathtt{\underline{ffdef}}}}\>:\>\mathcal{D}\\!\dagger\\![\texttt{ffid}\mapsto(\texttt{freefun,
ffid, {\text@underline{ffdef}}})],\mathcal{P}}$ Figure 13: Additional basic
semantic rules to support JLucid

###  3.2 Objective Lucid: JLucid with Java Objects

####  3.2.1 Rationale

Objective Lucid is a direct extension of JLucid. The original syntax of
Indexical Lucid (and also for JLucid and GIPL) is augmented to support a so-
called dot-notation. This allows Lucid to manipulate grouped data by using
object’s methods. In fact, the idea is similar to manipulating arrays in
JLucid. The difference with the arrays is that they are manipulated as a
collection of ordered data of elements of the same type, to be evaluated in
the same context. However, an object that varies in some dimension implies
that all its members, possibly of different types, also potentially vary along
this dimension, but across objects, i.e. the objects themselves are not
intensional. An object can be thought of as a heterogeneous collection of
different types of members, which you can access individually using their
name, whereas arrays can be thought of as a homogeneous collection of members
that can be accesses individually using their index.

Just like JLucid [MPG05], Objective Lucid is being developed as a separate
specific intensional programming language (SIPL) within the GIPSY for the same
reasons: keeping the other implementations undisturbed and working while
experimenting on this particular implementation.

#####  3.2.1.1 Pseudo-Objectivism in JLucid

A pseudo-object-oriented approach is already present in JLucid. The program
presented in Figure 14 gives an example of a Java function returning an object
of type Integer.

    #JAVA

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

    int g()
    {
        return f().intValue();
    }

    #JLUCID

    A
    where
        A = g();
    end;

Figure 14: Pseudo-objectivism in JLucid.

In JLucid we are not able to manipulate this object directly in intensional
programming as Java does, though we can provide methods, such as g() to access
properties of a particular Java object from within JLucid. However, that
reduces legacy Java code reusability by forcing the programmer to add such
functions in his code to be able to use it in the GIPSY. Another example in
Figure 15 shows how one can make use of objects in JLucid by providing pseudo-
free Java accessors similar to getComputedBar() in the example. They are
pseudo-free because they don’t appear as a part of any Java class to a JLucid
programmer explicitly, but internally they get wrapped into a class when the
code is compiled.

    #JAVA

    class Foo
    {
        private int bar;

        public Foo()
        {
            bar = (int)(Math.random() * Integer.MAX_VALUE);
        }

        public int getBar()
        {
            return bar;
        }

        public void computeMod(int piParam)
        {
            bar = bar % piParam;
        }
    }

    int getComputedBar(int piParam)
    {
        Foo oFoo = new Foo();
        oFoo.computeMod(piParam);
        System.out.println("bar = " + bar);
        return oFoo.getBar();
    }

    #JLUCID

    Bar
    where
        Bar = getComputedBar(5);
    end;

Figure 15: Using pseudo-free Java functions to access object properties in
JLucid.

In Objective Lucid such explicit workarounds are not necessary anymore, but
this gives us some ideas about how to actually implement some features of
Objective Lucid in practice, i.e., the compiler can generate a number of
pseudo-free accessors to object’s members and use JLucid’s implementation of
Java functions internally.

#####  3.2.1.2 Stream of Objects

An interesting question could be to ask: “What is an object stream?” Is it
that the members of this object vary in the same dimension(s) or they can have
“substreams”? In Objective Lucid we answer this as decomposing public object’s
data members into primitive types and varying them or in simplified manner we
employ object’s effectors. Thus, when there is a demand say for the object’s
state (data members) at some time $t$, there will have to be generated demands
for all of $t$ between $[0,t]$ where at time $0$ an instance of the object is
created. Therefore, the object state changes in the $[0,t]$ interval represent
the object stream in the context of this thesis. There are two possible
outcomes of this evaluation: either a portion of object’s state is altered by
an intensional program or the entire object. In the former case, Lucid only
accesses some object’s members via the dot-notation in the intensional manner,
whereas in the latter case all the members of an object are altered in the
intensional context implicitly. The examples presented in Figure 16, Figure 4,
page 4, and Figure 6, page 6 work on portions of an object, whereas the
examples in Section 4.1.3.6, page 4.1.3.6 work on all the members of an object
at the same time.

#####  3.2.1.3 Pure Intensional Object-Oriented Programming

Objective Lucid has presented a way for Lucid programs to use Java objects.
This may seem rather restrictive and may look like a workaround (though
practical!). An interesting concept would be to extend the Lucid language
itself to create and manipulate pure Lucid objects, not Java objects. This
will allow addressing issues like inheritance and polymorphism and other
attributes of object-oriented programming and will solve the problem of
matching Lucid and Java data types. This is not addressed in this work, but
attempted to be solved in [WP05].

####  3.2.2 Syntax

The parser is extended to support the `<objectref>.<feature>` dot-notation for
the Lucid part of reference data types. The semantic analysis is augmented to
accommodate objects and user-defined data types. In doing so, Lucid is able to
manipulate Java objects as well as access public variables and methods of
these objects. An example is shown in Figure 16. This example manipulates a
simple object E by evaluating its state at some time “2”. The program begins
with the construction of the object with f1() (or one could call the object
constructor directly), and then the rest of the expressions access public
members x and foo() of the object during expression evaluation.

    #JAVA
    class ClassXB
    {
        public int x;
        public float b;

        public ClassXB()
        {
            x = 0; b = 1.2;
        }

        public int foo(int a, float c)
        {
            return x = (int)(x * a + b * c);
        }

        ClassXB addx(int b)
        {
            x += b;
            return this;
        }
    }

    ClassXB f1()
    {
        return new ClassXB();
    }

    #OBJECTIVELUCID

    /*
     * The result of this program should be the object E
     * to be evaluated at time dimension 2 with its ’x’
     * member modified accordingly.
     */

    E @time 2
    where
        dimension time;
        E = f1() fby.time A;
        A = E.addx(B);
        B = E.foo(A @time C, A) + 3;
        C = E.x * 2;
    end;

Figure 16: Objective Lucid example.

The Objective Lucid syntax is in Figure 17. It is a direct extension of the
JLucid syntax in Figure 12 to support the dot-notation. Essentially, the
extension is the E.id productions. Any E on the left-hand-side can evaluate to
an object type, but the right-hand-side is always an identifier (Java class’
data member or method).

                    E      ::=   id
                            |    E(E,...,E)
                            |    if E then E else E fi
                            |    # E
                            |    E @ E E
                            |    E where Q end;
                            |    E bin-op E
                            |    un-op E
                            |    embed(URI, METHOD, E, E, ...)
                            |    E[E,...,E]
                            |    [E,...,E]
                            |    E.id
                            |    E.id(E,...,E)
                    Q      ::=   dimension id,...,id;
                            |    id = E;
                            |    E.id = E;
                            |    id.id,...,id(id,...,id) = E;
                            |    QQ
                    bin-op ::= fby | upon | asa | wvr
                    un-op  ::= first | next | prev

Figure 17: Objective Lucid Syntax

####  3.2.3 Semantics

To support these extensions to JLucid, the Semantic Analyzer of JLucid
requires more non-trivial changes than the syntax analysis and the dot-
notation implementation due to arbitrary object data types. In order to
perform type checks and apply the semantic rules of Lucid, we place the object
data types into the definition environment $\mathcal{D}$, which is in fact a
semantic equivalent to the data dictionary part of the GEER. This is partly
solved by using the pseudo-free Java functions, which de-objectify the object
members, but in order to be able to do so, we need to have the object types in
the definition environment. The corresponding operational semantic rules from
[Paq99] can be extended as follows.

The Objective Lucid extension to the operational semantics of Lucid is defined
in Figure 18. As in the original Lucid semantics, each type of identifier can
only be used in the appropriate situations. Notation:

  * •

class, cid, cdef means it is a Class type of identifier with name cid and a
definition cdef.

  * •

classv, cid.cvid, vdef means that the variable is a member variable of a class
classv with identifier cid.cvid given the variable definition vdef within the
class.

  * •

$\mathtt{<\\!\\!cid.cvid\\!\\!>}$ means object-member reference within an
intensional program.

  * •

classf, cid.cfid, fdef means that the function is a member function of a class
classf with identifier cid.cfid given the variable definition fdef within the
class.

  * •

$<\\!\\!{\mathtt{cid.cfid}}(v_{1},\dots,v_{n})\\!\\!>$ represents a object-
function call within an intensional program with actual parameters.

  * •

freefun, ffid, ffdef mean a type of identifier is a hybrid free (i.e. object-
free) function freefun, where ffid is its identifier and ffdef is its
definition (body).

  * •

By ${{\mathtt{\underline{cdef}}}}={\mathtt{Class\;cid\;\\{\ldots\\}}}$ we
declare a class definition. A class can contain member variable vdef and
member functions definitions fdef.

The rules:

  * •

The ${\mathbf{E_{c-vid}}}$ rule defines an object member variable for an
expression for the dot-notation. It is independent from the language in which
we define and express our objects. The rule says that under some context given
two expressions $E$ and $E^{\prime}$ that evaluate to a class-type identifier
$id$ and a variable type identifier $id^{\prime}$ respectively and if the two
together via a dot-notation represent an object-data-member reference, then
the expression $E.E^{\prime}$ evaluates to a value $v$.

  * •

Member function calls are resolved by the $\mathbf{E_{c-fct}}$ rule. Similarly
to the ${\mathbf{E_{c-vid}}}$ rule, it defines that given two expressions $E$
and $E^{\prime}$ under some context that evaluate to a class-type identifier
$id$ and a member function type identifier $id^{\prime}$ and a set of
intensional expressions ${E_{1},\ldots,E_{n}}$ evaluates to some values
${v_{1},\ldots,v_{n}}$ and the two identifiers via a dot-notation represent a
member function call with parameters ${v_{1},\ldots,v_{n}}$, then we say the
expression $E.E^{\prime}(E_{1},\ldots,E_{2})$ is a member function call that
under the same context evaluates to some value $v$, i.e. the function always
returns a value. Here we see why it is necessary for Lucid to map a void data
type to implicit Boolean true. This choice may seem a bit arbitrary (for
example, one could pick an integer $1$), but aside from practicality aspect
the mere choice of true may signify a successful termination of a method.

  * •

The ${\mathbf{E_{ffid}}}$ rule defines JLucid’s free functions. The rule is a
simpler version of $\mathbf{E_{c-fct}}$ with no class type identifiers
present.

  * •

The ${\mathbf{\\#JAVA_{objid}}}$ rule places class definition into the
definition environment.

  * •

The $\mathbf{\\#JAVA_{obvjid}}$ and $\mathbf{\\#JAVA_{objfid}}$ rules add
public Java object member variable and function identifiers along with their
definitions to the definition environment.

  * •

The JLucid $\mathbf{\\#JAVA_{ffid}}$ rule add free function definition to the
definition environment.

$\displaystyle{\mathbf{E_{c-vid}}}$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!:\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\frac{\begin{array}[]{c}\mathcal{D},\mathcal{P}\vdash
E:id\quad\mathcal{D},\mathcal{P}\vdash E^{\prime}:id^{\prime}\\\
\mathcal{D}(id)=({\texttt{class, cid,
{{\text@underline{cdef}}}}})\quad\mathcal{D}(id^{\prime})=({\texttt{classv,
cid.cvid, {{\text@underline{vdef}}}}})\\\
\mathcal{D},\mathcal{P}\vdash<\\!\\!{\mathtt{cid.cvid}}\\!\\!>:v\end{array}}{\mathcal{D},\mathcal{P}\vdash
E.E^{\prime}:v}$ $\displaystyle{\mathbf{E_{c-fct}}}$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!:\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\frac{\begin{array}[]{c}\mathcal{D},\mathcal{P}\vdash
E:id\qquad\mathcal{D},\mathcal{P}\vdash
E^{\prime}:id^{\prime}\qquad\mathcal{D},\mathcal{P}\vdash
E_{1},\ldots,E_{n}:v_{1},\ldots,v_{n}\\\ \mathcal{D}(id)=({\texttt{class, cid,
{{\text@underline{cdef}}}}})\qquad\mathcal{D}(id^{\prime})=({\texttt{classf,
cid.cfid, {{\text@underline{fdef}}}}})\\\
\mathcal{D},\mathcal{P}\vdash<\\!\\!{\mathtt{cid.cfid}}(v_{1},\dots,v_{n})\\!\\!>:v\end{array}}{\mathcal{D},\mathcal{P}\vdash
E.E^{\prime}(E_{1},\ldots,E_{n}):v}$ $\displaystyle{\mathbf{E_{ffid}}}$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!:\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\frac{\begin{array}[]{c}\mathcal{D},\mathcal{P}\vdash
E:id\qquad\mathcal{D},\mathcal{P}\vdash
E_{1},\ldots,E_{n}:v_{1},\ldots,v_{n}\\\ \mathcal{D}(id)=({\texttt{freefun,
ffid, {{\text@underline{ffdef}}}}})\\\
\mathcal{D},\mathcal{P}\vdash<\\!\\!{\mathtt{ffid}}(v_{1},\dots,v_{n})\\!\\!>:v\end{array}}{\mathcal{D},\mathcal{P}\vdash
E(E_{1},\ldots,E_{n}):v}$ $\displaystyle{\mathbf{\\#JAVA_{objid}}}$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!:\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\frac{{{\mathtt{\underline{cdef}}}}={\mathtt{Class\;cid\;\\{\ldots\\}}}}{\mathcal{D},\mathcal{P}\vdash{{\mathtt{\underline{cdef}}}}\>:\>\mathcal{D}\\!\dagger\\![{\mathtt{cid}}\mapsto(\mathtt{class,\;cid,\;{{\underline{cdef}}}})],\;\mathcal{P}}$
$\displaystyle{\mathbf{\\#JAVA_{objvid}}}$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!:\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\frac{{{\mathtt{\underline{cdef}}}}={\mathtt{Class\;cid\;\\{\ldots{\mathtt{\underline{vdef}}}\ldots\\}}}\qquad{{\mathtt{\underline{vdef}}}}={{\mathtt{public}\;type\;{\mathtt{vid};}}}}{\mathcal{D},\mathcal{P}\vdash{{\mathtt{\underline{cdef}}}}\>:\>\mathcal{D}\\!\dagger\\![{\mathtt{cid.vid}}\mapsto(\mathtt{classv,\;cid.vid,\;{\underline{vdef}}})],\mathcal{P}}$
$\displaystyle{\mathbf{\\#JAVA_{objfid}}}$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!:\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\frac{{{\mathtt{\underline{cdef}}}}={\mathtt{Class\;cid}}\;\\{\ldots{\mathtt{\underline{fdef}}}\ldots\\}\qquad{{\mathtt{\underline{fdef}}}}={\mathtt{public}}\;\mathit{frttype}\texttt{
fid}(\mathit{fargtype_{1}}\;farg_{id_{1}},\dots,\mathit{fargtype_{n}}\;farg_{id_{n}})}{\mathcal{D},\mathcal{P}\vdash{{\mathtt{\underline{cdef}}}}\>:\>\mathcal{D}\\!\dagger\\![\texttt{cid.fid}\mapsto(\texttt{classf,
cid.fid, {\text@underline{fdef}}})],\mathcal{P}}$
$\displaystyle{\mathbf{\\#JAVA_{ffid}}}$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!:\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!$
$\displaystyle\frac{{{\mathtt{\underline{ffdef}}}}=\mathit{frttype}\texttt{
ffid}(\mathit{fargtype_{1}}\;farg_{id_{1}},\dots,\mathit{fargtype_{n}}\;farg_{id_{n}})}{\mathcal{D},\mathcal{P}\vdash{{\mathtt{\underline{ffdef}}}}\>:\>\mathcal{D}\\!\dagger\\![\texttt{ffid}\mapsto(\texttt{freefun,
ffid, {\text@underline{ffdef}}})],\mathcal{P}}$ Figure 18: Additional basic
semantic rules to support Objective Lucid

###  3.3 General Imperative Compiler Framework

####  3.3.1 Rationale

Having to deal with JLucid, Objective Lucid, and Java and a future likely
possibility to include other than Java imperative languages into intensional
ones prompted invention of a general mechanism to handle that and simplify
addition of new languages into the GIPSY for research and experiments. This
generalization touches several critical aspects exposed by the JLucid and
Objective Lucid languages involving such a hybrid programming model. Thus, a
core redesign of the GIPC was necessary to enable this feature. The General
Imperative Compiler Framework (GICF) addresses the generalization issues
(split among this Methodology and Design and Implementation chapters) for the
imperative compilers and suggests later development of a similar framework for
the intensional languages.

The core areas in the hybrid compilation process affect the way an intensional
language program (which now syntactically allows having any number of code
segments written in one or more imperative languages) is compiled. This kind
of program has to be preprocessed first to extract the code segments to be
compiled by the appropriate language compilers and at the same time maintains
syntactic and semantic links between the parts of a hybrid program. This
influences the general intensional compiler instrumentation, such as
generation of sequential threads and communication procedures, function
elimination, GIPL-to-SIPL translation, semantic analysis, and linking (and
later interpreting/executing) of a GIPSY program.

Requirements for any such a framework like GICF imply at least the following
considerations:

  * •

having a number of compiler interfaces known to the system that any concrete
compiler implements,

  * •

ability to pick such compilers at runtime based on a hybrid program being
compiled,

  * •

have a generalized AST that is capable of holding intensional and imperative
nodes,

  * •

have the semantic analyzer understand possible data types that any language
may expose (which is a very challenging goal to do correctly), and deal with
function elimination for the imperative parts of the AST,

  * •

preprocess by breaking down a hybrid GIPSY program’s source code to be fed to
the appropriate compilers gives us flexibility of allowing to include any
imperative language we want, but complicates maintenance of semantic links
between the intensional and imperative parts for later linking and semantic
analysis. This necessitates development of the two other special segments that
can declare in a uniform manner for GIPSY providing some meta information
about embedded imperative sequential threads, like function and type
identifiers, parameter and return types for communication procedures, and user
data types. Thus, for the former we need a function prototype declaration
segment, that lists all free functions declared within imperative segments to
be used by Lucid and the type declaration segment for the user-defined types
possibly declared in those same imperative segments. The purpose of this meta-
information is two-fold: it will help us maintaining the semantic links via a
dictionary and create so-called “imperative stubs”. The former prompts the
development of the GIPSY Type System (see Section 4.1.1.5, page 4.1.1.5) as
understood by the Lucid language and its incarnation within the GIPSY to
handle types in a more general manner. The latter stubs have to be produced in
order for the intensional language compilers (that stay intact with the
introduced framework) not to choke on “undefined” symbols that really were
defined in the imperative parts, which an existing intensional compiler
running in isolation fails to see.

  * •

After all involved compilers are finished doing compilation of their code
segments, they all produce a partial AST. For intensional compilers that means
the main AST with the intensional and stub nodes. For imperative compilers it
is the appropriate imperative AST for each sequential thread. The imperative
AST, in fact, need not to be a real tree and may contain a single imperative
node that would hold a payload of STs (compiled object or byte code), CPs,
type information, and some meta-information (e.g. what language the STs and
CPs are in and for which operating system and native compiler environment).

  * •

Then, the imperative stubs have to be replaced by the real imperative nodes at
the linking stage before the semantic analysis.

  * •

Once the main tree is formed, the semantic analyzer would use the type system
to verify type information of the intensional-imperative calls within taking
into consideration imperative nodes when doing function elimination and
producing the final “executable” tree, or Demand AST, or DAST, a component of
the GEER.

All this work is motivated by the desire to simplify the addition of new
compilers into the GIPSY environment with minimal integration hassle. The
follow up sections explore some of the issues about primary matching of the
Java and GIPSY data types, followed by the definition of sequential threads
and communication procedures in the GIPSY, and their Worker aggregator. While
the below are sections that lay down a concrete example based on JLucid and
Java, the discussion addressing the generalization of the design and
implementation of these issues are presented in the chapter that follows with
the actual sequence diagram showing implementation details of the above hybrid
compilation process.

####  3.3.2 Matching Lucid and Java Data Types

Allowing Lucid to call Java functions brings a new set of issues related to
data types. Additional work is required on the semantic analyzer, especially
when it comes to type checks between Lucid and Java parts of a JLucid program.
This is pertinent when Lucid variables or expressions are used as parameters
to Java functions and when a Java function returns a result to be assigned to
a Lucid variable or used in an IP expression. The sets of types in both cases
are not exactly the same. The basic set of Lucid data types as defined by
Grogono [Gro02b] is int, bool, double, string, and dimension. Lucid’s int is
of the same size as Java’s int, and so are double, boolean, and String. Lucid
string and Java String are simply mapped to each other since internally we
implement the former as the latter; thus, one can think of the Lucid string as
a reference when evaluated in the intensional program. Based on this fact, the
lengths of a Lucid string and Java String are the same. Java String is also an
object in Java; however, at this point, a Lucid program has no direct access
to any object properties. We also distinguish the float data type for single-
precision floating point operations. The dimension index type is said to be an
integer for the time being, but might become a float when higher precision of
points in time, for example, will be in demand, or it could even be an
enumerated type of unordered values (though float dimensions will introduce
some very interesting problems). Therefore, we perform data type matching as
presented in Table 1. The return and parameter types matching sets are not the
same because of the size of the types. Additionally, we allow void Java return
type which will always be matched to a Boolean expression true in Lucid as an
expression has to always evaluate to something.

Table 1: Matching data types between Lucid and Java. Return Types of Java Methods | Types of Lucid Expressions
---|---
int, byte, long | int
float | float
double | double
boolean | bool
char, String | string
void | bool::true
Parameter Types Used in Lucid | Corresponding Java Types
string | String
float | float
double | double
int, dimension | int
bool | boolean

The table does not reflect the fact that JLucid is able to manipulate arrays
of values (streams), but these arrays are not Java arrays (Java’s arrays are
objects). In Objective Lucid (see Section 3.2), we also have Java object data
types will also be manipulated by a Lucid program with the Lucid part being
able to access object’s properties and methods and have them as return types
and arguments. As for now our types mapping and restrictions are as per Table
1.

####  3.3.3 Sequential Thread and Communication Procedure Generation

#####  3.3.3.1 Java Sequential Threads