Abstract Programming in Declo-Perative Languages.

The specification IS the design!

DJ Greaves. Under Construction: May/June 2003.

Summary

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.

Introduction

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:

  • 1. Determinstic and decideable compilation, and
  • 2. Programmer's control over run-time growth rates.

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.

Body

The body of this monograph is not written yet, although I am sure it will be very interesting.

Conclusion

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.

References

[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.