Subject: Re: Patterns and Compositionality - msg#00138

List: os.tunes

Date: Prev Next Index Thread: Prev Next Index

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

Was this page helpful?

Thread at a glance:

Previous Message by Date: click to view message preview

Re: Joy, Lambdas, Combinators, Procedures

> > Eh? Hmm, Haskell, for example, is not purely applicative. It has > > a lambda construct, and also a strange (pattern-matching) definition > > construct. This is along with its strange constructs that involve > > types. These constructs, it seems, are not syntactic sugar, but > > essential constructs to the system. > > [...] > > Oh, and BTW, the very existence of a lambda construct goes a long way to > proving that Haskell is applicative. A lambda expression is only meaningful > when it can be applied. I believe this reply is based on a misunderstanding of what I meant by "purely applicative". By a "purely applicative" language I mean a language which has _only_ an application construct, and no other constructs (other than primitives). So, since Haskell has a lambda construct (a construct other than application), it is not purely applicative. Purely applicative languages (in the sense that I mean) do not have lambdas or named variables of any kind. > > In case this was not clear, by "purely applicative language", I mean > > a language in which all expressions are built from a finite set > > of primitives using a binary construct ("function application"). > > An expression in such a language is most naturally written > > using a binary tree, with primitives as leafs. > > This is a definition which fails to define. Joy fits that definition > exactly, as does every language which uses finite-length identifiers. No, Joy has an odd construct for quotation, with those "[]"s. This is a construct other than application. > Unless you're implying that infix isn't allowed, in which case most > languages are excluded (but not Joy). Strictly, infix constructs other than application are not allowed in a purely applicative language; however, a language that has an infix construct can usually be reformalized without it, using a new function primitive. > An applicative language any language which has application. Application is I'll take that as a definition here... But remember that that is not what I mean by a "purely applicative" language. > the action of assigning a language element as being exclusively the property > of a function invocation. For example, in the C function call > "unlink(filename+1);" the function 'unlink' is being applied to the > syntactic element 'filename+1'. No other function is being given that > particular element; in fact, it may be impossible to reproduce, as for > example the C call "unlink(filename+rand());". I'm not sure what you mean by this... This seems to be part of an extended definition of "application", I guess... > > > > [purely applicative systems] > > > The benefits are very > > > well-known -- but the drawbacks are as well. > > > Hmm, what drawbacks are you speaking of? > > First of all, the names. Because parameters are syntactically tied to the > function to which they're applied, if you're going to use them more than > once you need to give them a name. The presence of this name forces you to > apply certain rules to the language's semantics beyond those which are > strictly required by the mathematics. Once again, a purely applicative system (in the sense that I meant) does not use names for its parameters. Purely applicative systems instead tend to use combinators (primitive functions such as "B", which composes a function, and "C", which swaps its parameter order, and others) to form functions. With a handful of such primitive functions, it is possible to form any function that could have been formed with a lambda (named variable) construct. > In addition, because function invocation is complicated by function > application, proofs written in the language have to deal with the double > action. The system you're describing (C, I believe) is nothing like a purely applicative system. > > Anyway, one clear benefit of using a purely applicative language > > is that it has such an amazingly simple syntax. > > I strongly suspect that you don't have a referent for "simple syntax". > Currying (the simplest known way to define an applicative language) is > indeed simpler than some of the complex parsing tricks some languages have > to do; however, currying is not enough by itself. You also have to have > four other syntactic elements: one to delimit functions, one to define > names, one to count how many parameters a function has (and identify each > one), and one to change the curry order. That's a total of five elements. Again, this is based on a misunderstanding... A purely applicative system does not use named parameters, and does have a truely simple syntax. > [made-up applicative language...] I think maybe another example may help... In a Joy test library, I saw this definition of "factorial": [ [pop 0 =] [pop succ] [[dup pred] dip i *] ifte ] y In a purely applicative language, a factorial function might be written as: Y (S3 (ifte =0) (K 1) . S times . CB (minus 1)) Or, without the sugar for composition ("."), Y (B (S3 (ifte =0) (K 1)) (B (S times) (CB (minus 1)))) where Y, B, S, S3, K, and C are certain primitive functions, with these rewrite rules: Yf = f(Yf) Bfgx = f(gx) Sfgx = fx(gx) S3 f g h x = fx(gx)(hx) Cfxy = fyx Hopefully you do not see a purely applicative approach as all so bad now, seeing how similar in spirit it is to Joy. > > In fact, the > > syntax of a purely applicative language is simpler than the syntax > > of a Joy-style expression. The essential construct of Joy is > > the list ("quoted program"); the other constructs (such as the > > finite-set construct and number-literal construct) could be > > eliminated. > > So, the format of a Joy expression is a tree (with primitives > > at the leafs), > > Something happened to the rest of this paragraph. I'm not sure what you > were trying to say, so I'd better not try to reply :-). Let me clarify... It should be clear that the list construct (written using "[" and "]") is the most fundamental construct of Joy. If the extras of Joy were omitted, the syntax of a Joy program would be basically a list of expressions (programs to execute), where each individual expression is either a primitive program (like "pop" or "dup") or itself a list (using "[]"s) of expressions. Anyhow, the whole point of this was to show that Joy's syntax is a bit more complicated than a purely applicative one. > > > > Hmm... I've never heard of "J" or "APL"... > > > > Oh no! APL's a great system, lots of fun. I recommend you start by > > > learning J, since it uses ASCII characters (instead of > > > APL's character set, > > > which requires not only extra characters, but even depends > > > on being able to > > > overstrike them). APL itself is a good language, but it's > > > hard to learn without a special keyboard (IMO). > > > I might have to check it out, then... is there a freely > > available system? > > Yes. It's an obsolete variant of a now-commercial system, but it still > works. It's at ftp://archive.uwaterloo.ca/languages/j. (There may be other > implementations there by now; however, it's a sophisticated language even > though it has a simple syntax.) I'll check it out... > > - "iepos" (Brent Kerby) > > -Billy > I hope this has cleared things up... - "iepos" (Brent Kerby)

Next Message by Date: click to view message preview

RE: Patterns and Compositionality

> From: Francois-Rene Rideau [mailto:fare@xxxxxxxxx] > > 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. I didn't say it was impossible -- I said that it's not easy. In fact, it's quite hard; proofs involving the resulting messes are a nightmare. > 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. Nonsense! Computers and even turing machines handle those _easily_. You're confusing one notation with absolute truth. > 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. Have you seen the proofs on similar systems written using abstract state machines? The proofs are readable by anyone with a reasonable amount of perseverence. > > 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', you're too hung up on formality. Not everything has a formal definition! "Design Patterns" are like "sewing patterns". Opposing them is like opposing sewing patterns because they're only shapes, and geometricians have known about shapes all along. A realistic definition of a "pattern" in that sense is "how it's been done before". Perhaps the words "role model" serve better. Of course, some people give "patterns" a more rigorous definition. I haven't seen a single one which didn't make me think it was total and utter hype; but that's probably because I'm prejudiced. At the same time, it does seem reasonable to me that because the general concept of "patterns" is so solidly established and has been proven so useful, any specific definition should politely use another name. > > 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. It's one of the more important things I said. Patterns are useful and expedient. TUNES is also useful, but not always expedient. Hype claims to be useful, but is never expedient. TUNES is closer to hype than patterns are. > [ François-René ÐVB Rideau | Reflection&Cybernethics | -Billy

Previous Message by Thread: click to view message preview

On Christopher Alexander (was: Patterns and Compositionality)

Jim Little wrote: > > This is exactly the point I was trying to address in my original post: > > Massimo Dentico wrote: > > *if* the substitution process (generalizing/inlining) for > > patterns in OOD is equivalent to the substituition process in > > functional/logic languages (pattern matching) [...] > > It is not equivalent. > > Design patterns in OOD are not substituted, generalized, or inlined. > The concept has no meaning for design patterns. Design patterns are a > way of communicating knowledge. They're written in natural language for > use by human observers. To use a design pattern, you read it, > internalize it, and intuit its applicability to your design. Good > design is a matter of communication and understanding, not > functionality, and as such it simply can't be formalized or automated. > As a tool for communicating "good design," neither can design patterns. > > Comparing design patterns to pattern matching in functional languages is > a fallacy. They are not comparable. > > Jim > > PS: I'm not trying to address the rest of the discussion -- I'm just > trying to clear up a pretty strong misunderstanding about the nature of > design patterns. About possible "formalization" of patterns, this post could have as subject: commercial vulgarizers(?) considered *extremely* harmful. Jim, I suggest to read this: "SOME NOTES ON CHRISTOPHER ALEXANDER. By Dr. Nikos A. Salingaros, mathematician and architectural theorist." - http://www.math.utsa.edu/sphere/salingar/Chris.text.html IMHO is an extremely interesting reading. It completely rehabilitates the subject of patterns to my eyes. So, thanks for the discussion. ================================================================== [...] PUBLICATIONS Dr. Alexander is the author of numerous books and papers. He has initiated a new approach to architectural thinking, in which the same set of laws determines the structure of a city; a building; ^^^^ or a single room. He has spent most of his life in searching for these laws. His approach to solving this universal problem takes advantage of scientific reasoning, and totally opposes other, ^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^ unscientific approaches based on fashion, politics, or arbitrary ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ personal ideas. This is so different from the way architecture has ^^^^^^^^^^^^^^ been taught since the second world war that it causes conflicts with established architectural schools. Alexander offers definitive solutions to the problems of urban architecture and design. It is a great pity that these were not adopted when first published. Fortunately, a small number of his ideas have been incorporated into the "New Urbanism". Nevertheless, this very recent movement by no means represents a wholesale application of his results. Alexander has actually ^^^^^^^^^^^^^^^^^^^^^^^ abstracted the process by which organic and inorganic forms evolve ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ -- which is the same process that governs the growth of a city. These results lie at the basis of how matter organizes itself ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ coherently, and are the opposite of the modern planning approach in which grids, zones, roads, and buildings, based on some preconceived design on paper, are imposed on human activity. These results will be expounded at length in the four-volume The Nature of Order, which is now being prepared for publication. [...] INFLUENCE ON COMPUTER SCIENCE [...] One of the most influential persons in the "Patterns Movement", James Coplien has posted a History of Patterns, and is doing pioneering work on applying patterns to human organizations (see next section). He also has embarked on a search for the deep ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ geometrical structures in software that correlate with "beauty" ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ and "order" in architecture and nature. This fascinating ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ development, based on Alexander's The Nature of Order, is being documented in a series of articles published in the C++ Report. They are all accessible from the index site Geometry In Code. ^^^^^^^^^^^^^^^^ Pattern languages have been developed for many diverse specific disciplines that relate to computer science, such as individual applications and computer-human interfaces. Tom Erickson has collected links to Pattern Languages for Interaction Design. These include user-interface pattern languages. The pattern ^^^^^^^^^^^^ language developed by Jenifer Tidwell is especially comprehensive, ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ and addresses the problems inherent in the design of any complex ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ or interactive artifact. Although, as in all links in this ^^^^^^^^^^^^^^^^^^^^^^^^^ section, this is written by a computer scientist, it in fact answers questions about general design first raised in the 1960's (by people such as B. Archer, C. Jones, H. Rittel, and H. Simon) that were judged to be too complex to solve. INFLUENCE ON INFORMATION STRUCTURES AND ORGANIZATIONS Certain computer scientists have taken Alexander's ideas beyond their initial application to the internal organization of computer ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ programs, into the software development process itself. As ^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Alexander's results are entirely general, they also apply to the internal structure of organizations and corporations. This very exciting development is now growing rapidly into an entirely new business discipline. Such an innovative (and entirely logical) application of Alexander's results could start a new approach to organization in the commercial and government sectors. There are very strong hopes at this time that an Alexandrine analysis and application of organizational patterns can redesign corporations. ================================================================== -- Massimo Dentico

Next Message by Thread: click to view message preview

Loading Comments...