Patterns and Compositionality

Massimo Dentico
Wed, 26 Jan 2000 20:54:55 +0100

A citation from  "Interaction, Computability, and Church’s Thesis"
P. Wegner, p. 18

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

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:

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