*CTL*

20 décembre 2010 - 14h00

La programmation Cartésienne (Habilitation à Diriger des Recherches) (HDR)

par John Plaice de University of New South Wales

Abstract: We present a new form of declarative programming inspired by the Cartesian coordinate sys-

tem. This Cartesian programming, illustrated by the TransLucid language, assumes that all

programmed entities vary with respect to all possible dimensions, or degrees of freedom. This

model is immediately applicable to areas of science, engineering and business in which working

with multiple dimensions is common. It is also well suited to specification and programming in

situations where a problem is not fully understood, and, with refinement, more parameters will

be taken into consideration as time progresses.

In the Cartesian model, these dimensions include, for all entities, all possible parameters, be

these explicit or implicit, visible or hidden. As a result, defining the aggregate semantics of an

entire system is simplified, much as the use of the universal relation simplifies the semantics of a

relational database system. Evolution through time is handled through the use of a special time

dimension that does not allow access to the future.

In TransLucid, any atomic value may be used as a dimension. A context maps each dimension

to its corresponding ordinate. A context delta is the partial equivalent. An expression is evaluated

in a given context, and this context may be queried, dimension by dimension, or perturbed by a

context delta.

A variable in TransLucid may have several definitions, and given a current context, the bestfit

(most specific) definitions with respect to that context are chosen and evaluated separately, and

the results are combined together. The set of definitions for a variable define a hyperdaton, which

can be understood as an arbitrary-dimensional array of arbitrary extent.

Functional abstraction in TransLucid requires two kinds of parameters: value parameters, with

call-by-value semantics, are used to pass dimensions and constants; named parameters, with call-

by-name semantics, are used to pass hyperdatons. Where clauses, used for local definitions, define

both new variables and new dimensions of variance.

This thesis presents the full development of Cartesian programming and of TransLucid, com-

plete with a historical overview leading to their conception. Both the denotational and operational

semantics are presented, as is the implementation, designed as a library. One important result is

that the operational semantics requires only the evaluation and caching of relevant dimensions,

thereby ensuring that space usage is kept to a minimum. Two applications using the TransLucid

library are presented, one a standalone interpreter, the other an interactive code browser and

hyperdaton visualizer.

The set of equations defining a TransLucid system can vary over time, a special dimension. At

each instant, the set of equations may be modified, but in so doing can only affect the present and

future of the system. Timing semantics is always synchronous. There are several possible ways

for multiple TransLucid systems to interact.

The caching mechanism provided in the operational semantics allows for the efficient imple-

mentation of systems whose calling structure is highly irregular. For more regular structures, it

is possible to create even more efficient bottom-up solutions, in which recursive instantiations of

functions are eliminated, with clear bounds on memory usage and computation.

Cartesian programming is not just designed as a standalone paradigm, but as a means of better

understanding other paradigms. We examine imperative programming and side-effects, and show

that these, under certain conditions, can be translated into TransLucid, thereby allowing the

design of new imperative constructs in the original language.