DJ Greaves. Under Construction: May/June 2003.
We use the term 'declo-perative' to describe
programming languages that embody both declarative and imperative
constructs. Both forms may make use of function definitions and
wrap-up their code using a module system, and so all major forms of
programming and system design are seamlessly combined.
By 'declarative' we mean that the user can
enter logic expressions, that are implicitly universally quantified over
time, which describe the allowable and unallowable behaviour of the
system or program, or parts of it.
By 'imperative' we mean that the user declares
mutable objects that carry state (variables), and also a sequence of
commands that operate on them to achieve the desired behaviour of the
system or program.
In this monograph, we argue that totally new, general purpose,
programming languages will be used in the future. These high-level
languages (HLLs) will provide not-only conventional assignment and
function call, but a raft of more powerful primitives, including
linear programming, regular expressions, stable marriage, model
checking and further scheduling and resource allocation primitives.
Although imperative programming has dominated the world of
computing for 50 years or more, many people now recognise that we must
move to higher-level languages to avoid bugs and to enable more of the
work to be done by the compiler. Many programming tasks require
programs to behave according to formal specifications. Where
available, it is only natural to try to use these specification
directly in the program and to ask the compiler to generate conforming
implementations. However, we must consider whether such programming
languages can always compile and type-check in bounded time ?
So far, successful declarative languages for program and system
implementation include mainly executable specification languages, such
as Prolog and Mercury. Escher is a mixed mode language where the
ports to a function can be tagged to provide a seamless integration
of functional and declarative programming within a common syntax.
However, it is essentially a variation on the executable specifications
of Prolog and Mercury. Rosetta [8] is a specification language with similar
facilities.
Clearly we wish to move away from executable specifications towards
more general declarative approaches. But for the success of a HLL,
we must not lose two important properties:
These two can be paraphrased as compile-time and run-time respective
expectations of execution time. We might argue that the second is
more important, which suggests that we are free to add functionality
to compilers but not to run-time systems. (The importance of the
second point is perhaps well-illustrated by the current lack
of success of functional languages for commercial programming
applications: most packages leave the garbage collection overhead
entirely to run-time, whereas for commercial success, a strong
level of control at compile-time is probably required.)
The functionality we wish to add to our general-purpose HLL
consists of new datatypes and a raft of well-known algorithms from fourth-generation
languages. Apart from the prolog-style resolution, we can consider
refinement, integer linear programming, regular expressions, stable marriage,
associative arrays, model checking and a class of scheduling and
resource allocation primitives. The new datatypes are sets and sequences
in addition to objects, matrices, arrays, stacks and lists.
The body of this monograph is not written yet, although I am sure
it will be very interesting.
We have argued (or will have done in the final version!) that
it is time to augment the toolkit of HLL compilers. Both forms
of behavioural programming, imperative and functional, do not
require the compiler to be creative in terms of algorithm design.
They cannot easily generate code for parallel execution platforms
and custom VLIW processors, but the importance of these platforms
for application-specific purposes is growing rapidly. Therefore
souce code for these targets is frequently non-portable.
We are certainly not arguing that all algorithm design should
be performed by compilers. Instead, we argue that it is time to
give the compiler more freedom in this respect, while maintaining
full compatibility with conventional behavioural styles, where
the user can take control as required.
[1]. J.W. Lloyd. Declarative Programming in Escher. Technical Report CSTR-95-013, University of Bristol, 1995. http://citeseer.nj.nec.com/lloyd95declarative.html
[2]. http://www-2.cs.cmu.edu/Groups/AI/html/faqs/lang/prolog/prg/part2/faq-doc-0.html
[3]. International Journal in Computer Simulation, Volume 4 Joseph
Buck, Soonhoi Ha, Edward A. Lee, David G. Messerschmitt: Ptolemy: A
Framework for Simulating and Prototyping Heterogenous Systems
[4]Constraint-Based Embedded Program Composition
http://www.isis.vanderbilt.edu/Projects/PCES/default.html
[5]
A Higher Level System Communication Model for Object-Oriented Specification
and Design of Embedded Systems Kjetil Svarstad, Nezih Ben-Fredj et al
http://tima.imag.fr/SLS/documents/aspdac_Svarstad.pdf
[6]. Expect Perl.
http://melbourne.pm.org/talks/expect/
|
[7]. R. Paige and R. E. Tarjan. Three partition refinement algorithms. SIAM Journal on Computing, 16(6):973--989, Dec. 1987.
[8]. Rosetta.
(C) May/June 2003 DJ Greaves.