Patterns and Compositionality
Massimo Dentico
m.dentico@teseo.it
Thu, 27 Jan 2000 20:08:30 +0100
btanksley@hifn.com wrote:
>
> Massimo, why are all your messages sent with high importance? ("X-Priority:
> 1" in the header.)
For the strange behavior of my ISP POP3 server: sometimes it
delivers messages with low priority with days of delay or not
delivers at all. If this causes problems, I could try to send
messages with normal priority (like this).
> > From: Massimo Dentico [mailto:m.dentico@teseo.it]
> > Subject: Re: Patterns and Compositionality
>
> > Jim Little wrote:
>
> > The context is: "[..] If generalizing a pattern is lambda-
> > abstraction and inlining a pattern is beta-expansion [..]". So, I
> > have rendered explicit my premises just to make feasible an
> > objection to my reasoning. But the intuitive definition of pattern
> > doesn't invalidate /a priori/ a more rigorous one.
>
> Lambda calculus is not even _close_ to powerful enough to handle design
> patterns -- it's not even powerful enough to easily handle function calls
> when the called function is permitted to modify variables (although it is
> sufficiently powerful to model either one, given some more complexity). So
> you can't establish a one-to-one correspondance between operations in lambda
> calculus and pattern design or use.
I am trying to say exactly what you have written, sorry for my
English: *if* the substitution process (generalizing/inlining) for
patterns in OOD is equivalent to the substituition process in
functional/logic languages (pattern matching) *and* Wegner is
right *than* Lambda Calculus (LC) is an incomplete formalism even
for these languages (I want to remember that the substitution
process in LC becomes apparent in the laws of LC thus they define
the calculus and *precede* it). At least, this is what I
understand about the matter: misconception are attributable only
to me. The context is this:
==================================================================
[...] 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. [...]
==================================================================
>
> So far, patterns have no been successfully formalized. One reason for this
> is that a true design pattern has to be commonly useful; if it's not, it may
> be a clever design, but it's not suitable for a pattern.
>
> > I suspect that Fare speaks about the "hype" (I'm not sure about
> > the meaning of this word), around the useful idea of pattern,
> > exactly because the lack of a precise definition prevent any
> > attempt of rigorous reasoning (for example, comparisons of
> > expressiveness with other frameworks).
>
> Fare senses most strongly other's crimes when he himself is guilty of the
> same thing. Hype is the entire basis of our devotion to Tunes, and Fare is
> responsible for that. So hype can be used for good as well as evil ;-).
Ok, what means hype exactly?
> Patterns are useful. This is one of the main parts of their definition, so
> they can't help it.
>
> The patterns used in C++ are not similar to the patterns used in C, and
> neither one looks like the design patterns used in Beta (although the C++
> patterns are mostly useful in Beta, the other way is not true; some C++
> patterns are useless in Beta because Beta can express the same concepts as
> part of the language).
>
> > Instead the problem is: the rigorous definition cathces the whole
> > intuitive definition? The paper of Wegner (as I understand it)
> > tries to answer this question relatively to the notion of
> > computability, the intuitive compared to the formal notion. He
> > suggests that Multi-Stream Interection Machines (MIMs) and
> > co-inductive reasoning give a stronger model of computation
> > compared to Turing Machines, lambda calculus and inductive
> > reasoning.
>
> A very interesting hypothesis. I lost the link to it, I think; or I never
> read it. Where may I look?
Home page of Peter Wegner:
- http://www.cs.brown.edu/people/pw/
I'm writing about this paper, cited in my original post that
originate this thread: "Interaction, Computability, and Church’s
Thesis":
- http://www.cs.brown.edu/people/pw/papers/bcj1.pdf
> > The intention of my original post was to highlight the fact that
> > if Wegner and my equation are right then, even in the
> > field of functional/logic
> > programming, the formal model of reference
> > (lambda calculs) doesn't catch the expressive power of this
> > languages.
>
> Which language?
For example Haskell (functional) has pattern-matching and Prolog
(logic) has it as a fundamental mechanism that unify procedure
invocation (procedural interpretation) and data construction
and deconstruction.
> Or were you trying to say that lambda calculus can't model everything a
> computer can compute?
This is what stated Wegner. I want to highlight that even for the
languages that one suppose to be based on lambda calculus, this
formalism is not adequate to deal with their important features
like pattern matching.
I hope that this post is understandable.
--
Massimo Dentico