Patterns and Compositionality
Massimo Dentico
m.dentico@teseo.it
Wed, 26 Jan 2000 20:54:55 +0100
A citation from "Interaction, Computability, and Church’s Thesis"
P. Wegner, p. 18
- http://www.cs.brown.edu/people/pw/papers/bcj1.pdf
==================================================================
[...] Structured programming for actions (verbs) can be formally
defined by function composition, while structured object-based
programming for composite objects (nouns) is modeled by **design
patterns** that have no compositional formal specifications.
Compositionality is a desirable property for formal tractability
of programs that has led to advocacy of functional and logic
programming as a basis for computation. But it limits
expressiveness by requiring the whole to be expressible as the sum
of its parts. Actual object-oriented programs and computer
networks exhibit noncompositional emergent behavior. There are
inherent trade-offs between formalizability and expressiveness
that are clearly brought out by the expressive limitations of
compositionality. Arguments in the 1960s that go-tos are
considered harmful for formalizability can be paralleled by
arguments in the 1990s that compositionality is considered harmful
for expressiveness.
[...]
==================================================================
Some thoughts if all that it is true:
1) Joy takes to the extreme the idea of compositionality and easy
formal tractability but, so making, abdicates to a better
expressiveness (from the point of view of Wegner); any idea about
that?
2) If generalizing a pattern is lambda-abstraction and inlining a
pattern is beta-expansion (I am not aware of any formal definition
of "pattern" in "software engineering", so I suppose that equating
it with the "pattern" in functional and logic programming sense is
correct; is it the same in the Scandinavian school of OO (Beta)?)
the paper of Wegner gives an insight about the difficulties of the
substitution process mentioned, for example, in SICP:
==================================================================
"Despite the semplicity of the substitution idea, it turns out to
be surprisingly complicated to give a rigorous mathematical
definition of the substitution process. The problem arises from
the possibility of confusion between the names used for the formal
parameters of a procedure and the (possibly identical) names used
in the expressions to which the procedure may be applied. Indeed,
there is a long history of erroneous definitions of substitution
in the literature of logic and programming semantics. [...]"
Quoted from "Structure and Interpretation of Computer Programs"
(shortly SICP), 2nd Edition , Abelson and Sussman, p. 15, note 15
==================================================================
In some extent, the occur check (that prevent substitution in the
case of names collision) breaks the compositional character of the
substitution process (two way pattern matching, unification or
lambda-unification for lambda terms).
So, it's seem to me that is the formal framework of reference to
be inadequate, not the whole functional/logic languages as stated
by Wegner (some has pattern matching). For example, in the paper
"Formulating Haskell", p. 10, Simon Thompson wrote:
- http://www.cs.ukc.ac.uk/pubs/1992/123/index.html
==================================================================
8 Conclusion
The paper addresses the design of the Haskell programming language
from the point of view of giving (formal) proofs of correcness of
functional programs. It is evident that Haskell share the elegance
and simplicity of other lazy languages, but certain features cause
difficulties for the verifier. The ability freely to combine
**pattern matching**, guards and local definitions causes
difficulties beyond the advantage gained. [...]
==================================================================
Am I wrong?
--
Massimo Dentico