http://www.spinellis.gr/pubs/jrnl/1995-JOOP-Multipar/html/paper.html
This is an HTML rendering of a working paper draft that led to a publication. The publication should always be cited in preference to this draft using the following reference:

Citation(s): 2 (selected).

This document is also available in PDF format.

The document's metadata is available in BibTeX format.

Find the publication on Google Scholar

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Diomidis Spinellis Publications

Object-Oriented Technology in Multiparadigm Language Implementation

Diomidis Spinellis
Department of Computing
Imperial College of Science, Technology and Medicine
dds@doc.ic.ac.uk

Abstract:

Implementing multi-paradigm programming environments is difficult, as the complexities of language implementation are combined with the interactions between the different languages. Research so far was centered around judiciously choosing the best language features to include in a multi-paradigm language. Object-oriented technology can be used as a structuring mechanism for multi-paradigm systems allowing arbitrary languages to be mixed in a single system. Objects are used to encapsulate modules written in different languages and inheritance to model language extensions. Using this approach we have implemented a multiparadigm programming environment generator and used it to create a five language multiparadigm programming environment.

1 Introduction

Multiparadigm programming languages and systems, allow the implementation of applications in a number of different programming paradigms. This makes it possible for the application developer to implement each part of the application in the best suited paradigm. Thus for example in a stock market decision support system the market heuristics could be expressed in the logic programming paradigm, the capture of incoming data could be implemented in the imperative paradigm, and the analysis of it could be based on the functional paradigm.

Although multiparadigm systems can offer a number of advantages their use is not widespread. An important obstacle in their acceptance is the lack of a suitable structure that allows the efficient and flexible combination of different paradigms, yet isolates them from unwanted interactions. In the following sections we will examine how object-oriented technology can be used as a paradigm encapsulation mechanism for the design of multiparadigm programming environments. By the adoption of this approach the following problems can be addressed:

In section 2 we describe work related to multiparadigm programming and the use of object-oriented technology in this field. In section 3 we outline how multiparadigm programming systems can be modeled and implemented using our approach, and in section 4 we present a system built to support this development process. Finally, section 5 contains an example of an existing system and possible new applications of this approach.

2 Related Work

 In a survey of multiparadigm languages and systems we identified more than 90 systems that allow programming in more than one paradigm. Some prevalent paradigm combinations are the following: Although some systems incorporate object-oriented technology, its use is limited at the linguistic level i.e. the expression of an implementation using the multiparadigm system; our approach proposes the use of object-oriented technology at a meta-linguistic level i.e. the design and implementation of the multiparadigm system.

A structured approach towards multiparadigm programming that is not based on specific programming paradigms is described in [Zav89]. The subject of that research is however the semantic and verification issues related to multiparadigm programming, and not the use of object-oriented technology as a paradigm encapsulation mechanism. Objects evaluated in different paradigm contexts using different resolvers are discussed in [TOO86]. Under that approach unification and non-deterministic choice are provided as resolvers (similar to the functional programming lambda operator) that can be used to evaluate objects. The approach does not cater for different syntactic notations between paradigms, nor does it fully address the incorporation of additional paradigms.

3 Object-based Multiparadigm Systems

 Object oriented-technology can be used to model and structure multiparadigm programming systems by regarding a set of programming language implementations as a class structure. In the following paragraphs we will examine the roles of inheritance, classes and objects in a multiparadigm programming system.

A class structure is evident (though not expressly used) even in existing language implementations. At the root of such a class structure lies the machine language of the target computer architecture. All libraries and operating system software are available at that level. Subclassing from the machine language level in order to provide a readable description we obtain assembly language. All language tools that emit assembly language are subclasses of that level. However, a number of compilers use a still higher level language such as C for their portable output representation, so these are subclasses of the C language which in turn is a subclass of the assembly language. We stress that the above example is just an object-oriented view of the existing state of affairs. We used it just to provide an illustration of an example tree class structure. Other possible examples are the subclassing of a logic programming language to obtain constraint logic programming, or the subclassing of both functional and logic programming languages from a language that provides the term data structure and garbage collection of dynamically allocated objects.

Every language in the structure described above forms a class. The single class variable contains the data needed for the runtime implementation of that language, such as the machine registers, the stack etc. In addition, each language class contains methods for compiling objects into a suitable representation, initialising its runtime machinery and executing the compiled object code. The compilation and execution can be either implemented at the class level, or delegated to the superclass, by compiling code to the superclass language and invoking its execution method at runtime.

Having defined languages as classes, we can now see that objects are the modules that are expressed in a given language. Every such module consists of its source and compiled code, as well as its internal state (e.g. static variable values) in the form of instance variables. In addition every module can have an instance initialisation method to initialise the module state variables, or perform language specific initialisation (e.g. invoke static variable class constructors in an object-oriented paradigm implementation).


  
Figure 1: Programming paradigm classes and objects

Summarising, a multiparadigm programming system can be modeled using object-oriented technology by expressing every paradigm as a class, using objects to isolate program modules, and inheritance to capture language relationships. Figure 1 illustrates this relationship.

4 Multiparadigm Programming System Generators

 Multiparadigm programming environments are complex collections of a number of systems, such as compilers, run-time support libraries and the associated utility tools. In order to organise the task of creating such environments we envisage the realisation of meta-environments: multiparadigm environment generators. These offer facilities for making the task of developing multiparadigm programming environments as easy as possible. Multiparadigm programming environment generators are based on, the object-oriented approach we described in the previous section. Their existence ensures that the approach is followed, and ad-hocery avoided. Furthermore, the development time and implementation errors can be reduced. We hope that such systems can even be used to create specialised paradigms for one specific application. In this way we can provide a solid software engineering foundation for the concept of ``little languages'' [Ben88, pp. 83-100, 128-131] [Spi93].

In order to demonstrate this approach we implemented MPSS, a multiparadigm programming environment generator. In the following paragraphs we present its design and implementation. We chose to implement MPSS as a tool suite, as this would offer us flexibility, extensibility, integration with the development platform, and implementation ease. Our design however lacks in process enforcement, and user friendliness. Implementing multiparadigm programming environments, is not a trivial task. We expect the users of our generator, to know what they are doing.

4.1 Requirements

A multiparadigm programming environment generator must support the design based around objects. We consider the following services to be essential: The functions of the resulting multiparadigm programming environment can be divided in three areas:
1.
paradigm-specific compilers,
2.
paradigm combination support, and
3.
run-time support.
Ideally support for all these areas should be provided by the generator.

4.2 Generator Structure

Based on the requirements outlined in the previous section we can now describe the structure of a multiparadigm programming environment generator. Such a generator consists of a paradigm compiler, which takes the object description of a paradigm class and creates its compiler, and run-time support. Other, specialised tools, are used before the paradigm compiler to assist the process of creating paradigm implementations using existing compilers or tools. Generic run-time support must be provided where possible, to implement functionality that will be required for all multiparadigm programming environments: this avoids duplication of effort among multiparadigm programming environment implementors. Finally a `system wrapper' combines all the tools, documentation and run-time support objects into a single distributable system. The combination of these components can be seen in figure 2. In the following sections we will describe the functionality of each of these components in more detail.


  
Figure 2: Structure of a multiparadigm environment generator

For every paradigm, the implementor provides a paradigm class description file, that defines the paradigm class. This is then compiled by the paradigm description compiler provided by MPSS into a compiler for that paradigm. When the source code of all paradigms has been compiled a special link editor, the multiparadigm link editor, is invoked to link all the paradigm objects and associated support libraries together into a runnable system. Two additional tools detect and protect class private variables.

4.3 Paradigm Description Compiler

  The paradigm description compiler compiles a paradigm class description file into a compiler for that paradigm. Paradigm description files are text files containing definitions for class variables and methods. Possible variable and method definitions are: the instructions for compiling paradigm code, variables that need to be protected, and the run-time support library name. Some of the variables must be defined for every paradigm, others can be defined if relevant. The class variables currently supported are listed in table 1. In addition, the multiparadigm system builder can introduce more variables according to the structure of the system. For example, typechecking support can be added in the form of additional class methods.

Variables and methods are defined by the method or variable name starting at the beginning of a line, followed by a colon, followed by the value. Within the file, the programmer can refer to a variable value by using its name mapped to uppercase characters within curly brackets, preceded by a dollar sign, e.g. ${SELF.TOOL}. The variable SOURCE, is automatically set within the code generated by the paradigm compiler to reflect the name of the filename source parameter given by the multiparadigm programming environment user.


 
Table 1: Class variables supported by the paradigm compiler
Variable name Meaning
SUPER Superclass name (TARGET for root class)
TOOL Name of the compiler to generate
EXTENSION Paradigm source filename extension
COMPILE Compilation instructions
INSTANCEV Class member instance variables
SYSTEM Multiparadigm environment name (e.g. blueprint)
SYNOPSIS Summary of the paradigm's operation
SOURCE User filename parameter

The paradigm description compiler performs variable substitution for the variables of the class and its superclass using the usual  SELF. and  SUPER. variable prefixes. Using an undefined variable within a class description will produce a compilation error. A sample paradigm description file, is listed in figure 3.

  
Figure 3: Sample paradigm description file
# Paradigm description file for the backtracking paradigm
#
# $Id: btrack.pdef,v 1.2 1993/05/03 15:33:55 dds Exp dds $
# Environment name
system: blueprint
# Paradigm name
name: btrack
# Superclass name
super: term
# Source file extension
extension: pb
# Target tool name
tool: btrackpc
# Instance variables and functions.  These variables and functions are 
# duplicated across instances of the paradigms runtime machinery
instancev: rules_1 mpss_needlib_lbtrack_0 btrack_3
        tryall_5 solve_4 import_unify_3
# Compilation instructions
compile:
        rm -f ${SOURCE}.${SUPER.EXTENSION}
        bt2term ${SOURCE}.${SELF.EXTENSION} >${SOURCE}.${SUPER.EXTENSION}
        ${SUPER.TOOL} ${SOURCE}.${SUPER.EXTENSION}
# Runtime support modules
runtime: lbtrack.o
# Paradigm description for automatic manual creation
synopsis: backtracking and unification
description:
        \fIBtrack\fP is a pradigm for handling problems that can be
        solved using backtracking and unification.  The \fIbtrack\fP
        programming style intentionaly resembles that of Prolog.  Many
        pure Prolog programs can be ported to \fIbtrack\fP without change.

4.4 Support for Existing Tools

  High quality and efficient implementations of paradigms are costly to implement. For this reason a multiparadigm environment generator should allow existing systems to be used wherever possible. This means that mechanisms must be provided to make such systems conform to the conventions expected by the overall system design. These mechanisms must transform independent systems into encapsulated paradigm objects. Specifically, they should identify and deal with potential resource requirement clashes in areas such as name-space, memory usage, and non-reentrant functions.

One major problem when using existing tools is that of name-space pollution. Some tools create code with global identifier names (function or variable identifiers) that can not be specified or changed by the user. Such code can be used only once within a given program. This is for example, the case with the lex   and yacc utilities. Having such tools as part of a multiparadigm environment is not possible, as they can only be used to create a single instance of a code object. MPSS provides an instance variable detection tool, instancev, which when run on the object code that such a utility generates, prints a list of the global variables that are defined in it. These can then be listed in the instancev section of paradigm class description file to be automatically converted to private instance variables.

Many of the paradigm translators, either because they are built based on existing utilities, or because of the translator design, or due to features of the implemented language will contain global variables or procedures that should be private to the class instance. Protect is a tool of MPSS that generates unique identifier names. The names of the private variables and procedures are listed in the instancev section of the paradigm class description file. Given this name list, protect will create regular expressions, that when applied to the assembly language output of the target architecture paradigm will automatically convert them to class private variables by prepending to them the name of the module in which they occur. A limited version of this tool,  yyhide [Gli91] is part of the Andrew Toolkit [PHS+88]. Yyhide only deals with output generated from yacc and lex, while our tool can handle output from any program generator.

4.5 Generic Run-time Support

Many paradigms need run-time support. All classes contain a class instance initialisation method and all objects an object instance initialisation method. These methods must be called in the appropriate order during the startup sequence of a multiparadigm application. This can be complicated (as it deals with system-dependent process initialisation code). Furthermore this is functionality that will be needed by all multiparadigm programming environments. In order to avoid duplication of effort among the multiparadigm environment implementors, to ensure a correct and portable implementation, and to simplify the task of implementing a multiparadigm programming environment, this functionality can be provided by the environment generator. Environment implementors can then, directly plug it in their systems with minimum additional effort. The design and implementation of these functions is highly dependent on the target system. In an open object-oriented integrated environment (such as Smalltalk) it could be as easy as binding an additional method to the process class constructor. In a file-based system using a link-editor it could require modifying the link-editor, the system startup code, or providing a kernel within which multiparadigm applications are run.

MPSS contains support for the linking phase in the form of mpld: the multiparadigm link editor. In addition to the duties of the system link editor (resolving references between the modules, and creating executable code) [PW72], the multiparadigm link editor has three additional duties to perform:

The class initialisation is performed before the instance initialisation, as the second one might depend on an initialised class instance. Furthermore initialisation proceeds from the top to the bottom of the class hierarchy, as a class might depend on its superclass for its initialisation.

4.6 System Wrapper

  One further area where the multiparadigm environment implementor can be helped is that of the final packaging. Multiparadigm environments can consist of tens if not hundreds of separate elements, such as specialised tools, libraries, compilers, run-time support modules, documentation files etc. The process of organising these into a system distribution can be automated, minimising potential errors and relieving the implementor of this mundane and error-prone activity. The actual design and implementation depends very much on the target system, the distribution method and the range of activities that will be automated. These can reach from a simple system installation procedure in specified directories, to the creation of a distribution tape with installation instructions and printed manuals. Some explorative, rapid-prototyping development environments (such as Smalltalk ), make it difficult to separate a product from the environment where development has taken place. In such cases additional support will be required in order to make this distinction and create an isolated product.

Mpss provides the system wrapper, a tool that by reading the paradigm description files locates the parts of the programming environment and organises them into a suitable distribution format. This ensures that the system distribution and its updates can be created reliably and with the minimum effort.

4.7 Building a Multiparadigm Programming Environment

The following is a sample approach for building a multiparadigm programming environment using MPSS:

1.
Decide the programming paradigms that will be supported, and the names that will be given to their classes.
2.
  Organise the paradigms into a tree class structure. Paradigms that are extensions of another paradigm should have that other paradigm as their superclass. The target architecture paradigm must be at the root of the class tree. If two paradigms share an important characteristic, try to abstract that characteristic into a separate class which will be the common superclass of the two other classes.
3.
Every paradigm needs a   class definition file. This, as a minimum, must define:
4.
For every paradigm create a translator that transforms the code of that paradigm into code of the target architecture. This is normally done by translating into the code of its superclass and invoking the superclass compiler via SUPER.COMPILE.     The invocation code for that translator is given in the compile section of the paradigm class definition file.
5.
If an existing tool is used for translating the paradigm code use  instancev to find out which variables must be made private for every class member instance.
6.
If the code generated by the translation process contains some global variables that should be private to a class member instance, list those in the instancev section of the paradigm class definition file.
7.
Compile all class definition files to create the compilers for all paradigms.
8.
Wrap up the system, using the system wrapper, for distribution or installation.

5 Applications

 We used MPSS in order to implement blueprint, a multiparadigm system that offers the six paradigms listed in table 2. Its class structure is illustrated in figure 4. The system was implemented using paradigm description files, compiled by MPSS, existing tools (to implement the imper, bnf and regex paradigms), as well as compilers (term) and interpreters (fun, btrack) written in blueprint. Of the 4260 lines that comprise the implementation, 787 (18%) are part of the paradigm description files, with the rest divided among the other paradigms. Blueprint was used to implement an application that manipulates definite and indefinite integrals. The lexical analysis and parsing were performed in regex and bnf, the symbolic evaluation in btrack, the numeric evaluation in fun, and user interface and graphing functions in term and imper. The use of the different paradigms available under blueprint made the system a lot more concise and readable than a similar older system implemented in Modula-2.


 
Table 2: Blueprint paradigm classes
Class name Description
imper Imperative constructs
term Term handling
btrack Logic programming
fun Functional programming
bnf BNF grammars
regex Regular expressions


  
Figure 4: Blueprint class hierarchy

The use of object-oriented technology for structuring multiparadigm systems is not limited to the domain of programming language paradigms. One other possible application domain is that of multiparadigm document preparation systems. A sample class structure of such a system is shown in figure 5. The root class in such a configuration would be a low level page description language, similar to the one used for describing the end product. A possible example would be the Postscript language. The other paradigms would be organised as a class tree in the usual fashion, with lower level languages such as TEX, troff and   RTF "[*]" acting as the superclasses of higher level languages such as LATEX, mm, pic, and   Microsoft Word. Paradigm communication in this case means the integration of the output of the different paradigms into the final document. Many of the paradigms described, offer a facility for incorporating Postscript code this is one more reason for choosing Postscript as the common superclass.


  
Figure 5: Multiparadigm document processing

6 Conclusion

We have demonstrated that object-oriented technology offers a viable structuring mechanism for multiparadigm systems. Inheritance is used to abstract common features between languages, classes are used to encapsulate different languages, and objects are used to define program modules. This structure allows the implementation of multiparadigm programming system generators: toolkits that assist the creation process of multiparadigm programming systems. Using this technology we implemented a sample multiparadigm programming environment, and outlined one other possible application in a different domain.

We have not addressed the areas of paradigm inter-operation, type-checking and the efficiency of the resulting implementations. These are areas that need further research, in order to find how object-oriented technologies can best be applied to them.

Acknowledgements

I would like to thank Sophia Drossopoulou and Susan Eisenbach for their help during the conduct of this research. Support from the British Science and Engineering Research Council is gratefully acknowledged.

References

BDG+88
Daniel G. Bobrow, L. G. DeMichiel, R. P. Gebriel, S. E. Keene, G. Kiczales, and D. A. Moon.
Common Lisp object system specification, X3J13 document 88-002R.
ACM SIGPLAN Notices, 23, September 1988.
Special Issue.

Ben88
Jon Louis Bentley.
More Programming Pearls: Confessions of a Coder.
Addison-Wesley, 1988.

Bon91
Pierre Bonzon.
Processing functional definitions as declarative knowledge: A reduced bytecode implementation of a functional logic machine.
In H. Boley and M. M. Richter, editors, Processing Declarative Knowledge: International Workshop PDK '91 Proceedings, pages 271-278, Kaiserslautern, Germany, July 1991. Springer-Verlag.
Lecture Notes in Computer Science 567.

Coh86
Shimon Cohen.
The APPLOG language.
In Doug DeGroot and Gary Lindstrom, editors, Logic Programming, Functions, Relations and Equations, pages 239-276. Prentice Hall, Englewood Cliffs, NJ, USA, 1986.

Gli91
Bob Glickstein.
YYHIDE: A post-processor for Yacc and Lex files.
Part of the Andrew System, 1991.

GM87
Joseph A. Goguen and José Meseguer.
Unifying functional, object-oriented and relational programming with logical semantics.
In Bruce Shriver and Peter Wegner, editors, Research Directions in Object-Oriented Programming, pages 417-477. MIT Press, 1987.

McC92
Francis G. McCabe.
Logic and Objects.
Prentice Hall, 1992.

Mey92
Betrand Meyer.
Eiffel: The Language.
Prentice Hall, 1992.

MS90
Gerhard Mehldau and Robert A. Schowengerdt.
A C-extension for rule-based image classification systems.
Photogrammetric Engineering and Remote Sensing, LVI(6):887-892, June 1990.

Mul86
Carlo Muller.
Modula -- Prolog: A software development tool.
IEEE Software, 3(6):39-45, November 1986.

PHS+88
Andrew J. Palay, Wilfred J. Hansen, Mark Sherman, Maria G. Wadlow, Thomas P. Neuendorffer, Zalman Stern, Miles Bader, and Thom Peters.
The Andrew toolkit -- an overview.
In Proceedings of the Winter 1988 USENIX Conference, pages 9-22, Dallas, TX, USA, January 1988. Usenix Association.

Pra83
Vaughan Pratt.
Five paradigm shifts in programming language design and their realization in Viron, a dataflow programming environment.
In Conference Record of the Tenth Annual ACM Symposium on Principles of Programming Languages, pages 1-9, Austin, TX, USA, Januray 1983.

PW72
Leon Presser and John R. White.
Linkers and loaders.
ACM Computing Surveys, 4(3):149-167, September 1972.

SBK86
Mark J. Stefik, Daniel G. Bobrow, and Kenneth M. Kahn.
Integrating access-oriented programming into a multiparadigm environment.
IEEE Software, 3(1):10-18, January 1986.

Spi93
Diomidis Spinellis.
Implementing Haskell: Language implementation as a tool building exercise.
Structured Programming, 14:37-48, 1993.

Str86
Bjarne Stroustrup.
The C++ Programming Language.
Addison-Wesley, 1986.

TOO86
Ikuo Takeuchi, Hiroshi Okuno, and Nobuyasu Ohsato.
A list processing language TAO with multiple programming paradigms.
New Generation Computing, 4(4):401-444, 1986.

WW88
J. H. Williams and E. L. Wimmers.
Sacrificing simplicity for convenience: Where do you draw the line.
In Conference Record of the 15th Annual ACM Symposium on Principles of Programming Languages, pages 169-179, Januray 1988.

YS86
Jia-Huai You and P. A. Subrahmanyam.
Equational logic programming: An extension to equational programming.
In Conference Record of the 13th Annual ACM Symposium on Principles of Programming Languages, pages 209-218, St. Petersburg Beach, Florida, USA, Januray 1986. Association for Computing Machinery.

Zan84
Carlo Zaniolo.
Object-oriented programming in Prolog.
In 1984 International Symposium on Logic Programming, pages 265-270, Atlantic City, New Jersey, USA, February 1984. The Computer Society of the IEEE, IEEE Computer Society Press.

Zav89
Pamela Zave.
A compositional approach to multiparadigm programming.
IEEE Software, 6(5):15-25, September 1989.

Footnotes

...RTF
Rich Text Format: a common inter-application document exchange format.