Review
REVIEW
of a paper by Rudolf Berghammer
“On Using Composition in
Transformational Programming”
The
reviewed paper deals with research of
mathematical semantics of functions
defined in purely
applicative
programming language. Semantics of such
function is defined as the fixed point
of the
corresponding functional in the space of
continual mappings. Several theorems are
proved, defining
semantics of functions composition for
the concerned language. As the theorems
corollary, correct
rules for transformation of applicative
programs (schemata) are formulated that
under certain
conditions allow to obtain simple
equations for functions being
compositions of given functions.
Among these rules are functions
transformations in view of given
transformations of the subject
domain and values domain types of these
functions. The importance of such
transformations can be
explained as follows.
One
of the most powerful and commonly used
principles of program development is the
“divide and
rule” principle whose application
produces a program that can be viewed as
a composition of
functions (programs) solving more simple
tasks. Inadequate decomposition of a
problem often
results in very inefficient programs –
functions compositions. In order to
raise the composition’s
efficiency we try to derive from it
“direct” equations defining the
problem-solving function. The
results of the reviewed paper give us an
instrument for getting these equations (but
only on the level
of applicative programs).
The
effect of transformations described in
the paper is clearly demonstrated by
some examples
where applicative programs with
exponential complexity are being
transformed into polynomial
ones.
The
paper’s presentation is clear, proofs
are simple and comprehensible, the most
of the results from
the fixed points theory used by the
author are well known.
I
find it advisable to recommend the paper
for IFIP WC.
V.K.Sabelfeld,
The
USSR AS Comp. Center
Senior
Researcher,
Ph.D.
Back
|
