Patterns and Compositionality

[Francois-Rene Rideau]

> 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).

Of course it can! See the papers on Concurrent Haskell! Or see Clean, etc.
Just because you haven't seen it doesn't mean it's impossible.
And just because things have the same name "variable" doesn't mean
they have a one-to-one correspondance in all settings.
If variable modification is difficult to handle in lambda-calculi,
it's because it's something _intrinsicly_ difficult to handle.
Lambda-calculi are _simple_ _formal_ calculi. Try to account for the
semantics of variable modification in _any_ calculus, you'll end up
with something fairly complex. You end up with state being a monad,
and variable accessors (and modifiers) being monadic combinators
(and yes, the semantics of monads is intrinsicly coinductive).

Friends have done proofs of imperative programs (heap sorting, and more)
in Coq (a logic system based on pure typed lambda-calculus); it's possible,
but it's certainly not straightforward.


> 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.
Another reason is that if they tried to formalize it, pattern people would
see that it's a combination of hype, the bloody obvious, and long known
in formal calculi.


> 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 ;-).

No comment.


One thing when one says that "A cannot express B" is to clearly define
"A", "express" and "B".

[ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[  TUNES project for a Free Reflective Computing System  | http://tunes.org  ]
Watt refused applications for licenses to make engines under his
patent: he discouraged experiments by Murdoch with locomotive models;
he was hostile to the use of steam at high pressure; and the authority
he wielded was such as to clog engineering enterprise for more than a
generation.  If his monopoly had been allowed to expire in 1783
England might have had railways earlier.  If a similar privilege had
been extended to Arkwright - if, indeed, his wide patents had not been
annulled in 1781-5 - it is at least possible that a dead hand might
have rested on the cotton industry also, and that forces tending to
raise the standard of life of the poor would have been stifled.

    -- Ashton T.S.,
       An Economic History of England: The 18th Century.