capture of idioms and patterns

newer
ANNOUNCE: Utrecht Haskell Compiler...

Luc TAESCH

22 Sep 2010 22 Sep '10

4:14 a.m.

in real life I am doing architecture (appication and system) and I tend to see things differently with my haskell background. when reading what system XYZ does, I see folds, maps, lazy sort, memoisation , monads, etc...ie my mind apply idioms learned at code design level to architecture level So the following questions raised in me : - are there any prior art in documenting idioms and patterns in FP, and especially haskell. - have any work been done refering to architecture level , using these idioms, or "FP specific architecture"... (the idea germinated to extend the FP contiunum from code, design to architecture (and requirement) thank you, folks luc

Attachments:

attachment.html (text/html — 780 bytes)

Show replies by date

Johannes Waldmann

22 Sep 22 Sep

5:20 a.m.

...

- are there any prior art in documenting idioms and patterns in FP [...]

you got this backwards: what some folks call "idioms and (design) patterns" actually *is* FP, because it is just this: higher order functions. And it's been there some decades (lambda calculus). That also explains the absence of any Design Patterns/Gang-of-Four kind of book for Haskell - it's just not needed. (as you say, map and fold are your patterns.) Best - J.W.

ajb＠spamcop.net

23 Sep 23 Sep

2:24 a.m.

G'day all. Quoting Johannes Waldmann :

...

you got this backwards: what some folks call "idioms and (design) patterns" actually *is* FP, because it is just this: higher order functions. And it's been there some decades (lambda calculus). That also explains the absence of any Design Patterns/Gang-of-Four kind of book for Haskell - it's just not needed.

Err... no. The phrase "design patterns" is a shorthand for "vocabulary of engineering experience". Zippers, continuation passing style, Church encoding... these are not what FP "is", but they are specific techniques that engineers working in Haskell need to know to use the language effectively. You can think of design patterns as techniques that you need to overcome shortcomings in the language. That's why you need special techniques for, say, iterators in C++ or Java where in Haskell that comes more or less for free. But then, you need special techniques for mutable global state in Haskell, where in C++ or Java you get that for free. Or, to put it another way, nothing is ever free. There is no GoF-like book for Haskell because it's not an idea that needs promoting in printed form. We just point people to the wiki. Cheers, Andrew Bromage

Jason Dagit

5:58 p.m.

On Wed, Sep 22, 2010 at 11:24 PM, wrote:

...

There is no GoF-like book for Haskell because it's not an idea that needs promoting in printed form. We just point people to the wiki.

I think a book would/could still be beneficial even with the wiki. There are some learners who benefit more from having a big dead-tree tome to stare at than they do from a web of read-write articles. Jason

Jim Snow

24 Sep 24 Sep

3:21 a.m.

...

G'day all.

Quoting Johannes Waldmann :

...
you got this backwards: what some folks call "idioms and (design) patterns" actually *is* FP, because it is just this: higher order functions. And it's been there some decades (lambda calculus). That also explains the absence of any Design Patterns/Gang-of-Four kind of book for Haskell - it's just not needed.

Err... no.

The phrase "design patterns" is a shorthand for "vocabulary of engineering experience". Zippers, continuation passing style, Church encoding... these are not what FP "is", but they are specific techniques that engineers working in Haskell need to know to use the language effectively.

... An often-overlooked bit of trivia is that the first books on design

...

There is no GoF-like book for Haskell because it's not an idea that needs promoting in printed form. We just point people to the wiki.

Cheers, Andrew Bromage ______________________________________________ I think a "functional design-pattern" section on the Haskell wiki would be a good idea. I think the "patterns" framework is a good and useful one, if we can communicate properly what design patters are and how

ajb@spamcop.net wrote: patters were not in computer science, but rather architecture. I would recommend "A Pattern Language: Towns, Buildings, Construction" and "A Timeless Way of Building" by Christopher Alexander to anyone who is interested in a great example of how design patterns are supposed to work (or anyone interested in constructing an attractive and functional building). I've never read GoF (it seemed a bit too focused on object-oriented design for my tastes), so I don't know how closely it follows Alexander's conventions. "A Pattern Language" is essentially a compilation of a couple hundred patterns -- a great resource if you want to build a house, but it doesn't offer much insight into what a pattern is. "A Timeless Way of Building", on the other hand, describes what a pattern is and how to go about discovering, documenting, and organizing (and, often, discarding) them. I was initially skeptical of "patterns", as they seemed like a rather vague concept, but it's actually quite formal. A pattern consists of some context in which the pattern can apply, a conflict that arises within that context, and a satisfactory solution to that conflict. Described this way, a pattern is an idea that makes itself a target for criticism, because a detractor can point out that the given pattern doesn't apply to its context, or that it doesn't resolve the conflict, or there may be some other pattern that works in a broader context that fully covers the narrow context. However, this makes it much easier to distinguish good ideas from bad ones. One notion about patterns that I'm not sure whether the GoF authors were aware of, is that the patterns can be arranged into a directed graph, where the most general patters form a sort of root, and the more specific, narrow patterns form the leaves. (Ideally, you would have a tree, but you might not.) A common problem whether designing buildings or programs, is that you get halfway into the design and have to start over because you come across some constraint that can't be circumvented. By starting with the most general patterns and working down to the more specific ones, you can reduce the amount of backtracking you will have to do. they're supposed to work. I think a lot of the basic knowledge about functional programming patterns is already there, it just needs to be formatted properly. Do people think this is the right way to document the Haskell community's "oral tradition"? -jim

Andrew Coppin

23 Sep 23 Sep

4:58 p.m.

On 22/09/2010 10:20 AM, Johannes Waldmann wrote:

...

...
- are there any prior art in documenting idioms and patterns in FP [...] you got this backwards: what some folks call "idioms and (design) patterns" actually *is* FP, because it is just this: higher order functions. And it's been there some decades (lambda calculus). That also explains the absence of any Design Patterns/Gang-of-Four kind of book for Haskell - it's just not needed. (as you say, map and fold are your patterns.)

Or rather, in Haskell your design patterns are things like "accumulating parameters", "difference lists", "finally tagless", "combinator libraries" and the like. Sadly, in Haskell at least, most of these things are a kind of "oral tradition" which isn't actually written down anywhere. (Which means that basically the only way to learn Haskell is to hang around and ask lots of dumb questions and gradually learn by osmosis...)

John Zabroski

7:22 p.m.

On Wed, Sep 22, 2010 at 5:20 AM, Johannes Waldmann < waldmann@imn.htwk-leipzig.de> wrote:

...

...
- are there any prior art in documenting idioms and patterns in FP [...]

you got this backwards: what some folks call "idioms and (design) patterns" actually *is* FP, because it is just this: higher order functions. And it's been there some decades (lambda calculus). That also explains the absence of any Design Patterns/Gang-of-Four kind of book for Haskell - it's just not needed. (as you say, map and fold are your patterns.)

Best - J.W.

Most developers misunderstand the Gang of Four design patterns, including the authors. For example, the GoF State Pattern is described synchronously, but anyone who has thought about this is in deep detail, e.g. actor theory, knows that asynchronous transitions are possible and that the target state can be decoupled from the source state. In mathematics, the most basic way to understand this is through finite state automata, since an automaton is only dependent on its current state and input to determine the next transition. GoF confuses the issue by insistenting on synchronous communication between classes that represent states. GoF has subpar explanations, but please separate the intellectual wheat from the chaff. I have also heard some argue that GoF patterns all have the same structure. This is not true. I've heard confused programmers say that the Proxy pattern and the Decorator pattern "look the same". Decorators provide structural support of nesting and Proxies do not, but the key difference between the two is that a Decorator is about adding or removing properties *dynamically*, whereas a Proxy is about accessing existing properties through a known static structure. How does higher order (recursive) functions make such patterns obsolete? Some existing design patterns are applicable regardless of paradigm, and will continuosly get re-invented until people learn better and start to realize how general the patterns are. Example: Deterministic systems are easier to debug than non-deterministic systems, due to the fact non-deterministic systems cannot generalize the Kahn Principle (this is known as the Brock-Ackerman Anomaly). Ergo, one of the best things you can do as a programmer is isolate nondeterminism. Patterns for doing so have been known for decades in the embedded systems community, and go by names such as Processor-Actuator, Watchdog, etc. I've suggested to some interested in FRP research that they'd be wise to look at those patterns, not as competitors but as complementary material to enhance every student's ability to inhale the FRP approach. Otherwise you end up with an engineering discussion that is more focused on the cute details on FRP and not how to design good systems! Currently the functional programming research community seems very aware of GoF design patterns but completely unaware and/or uninterested by real-time design patterns. I predict this will change within the next 5 years. Luc Taesch, Probably my favorite book on the subject is Thomas Kuehne's Ph.D. thesis which went out of print within the last year, but is freely available from the author's page: http://c2.com/cgi/wiki?FunctionalPatternSystemForObjectOrientedDesign One of the patterns Kuehne discusses, Transfold, is something every computer scientist should understand. Unfortunately, the book uses the Eiffel language and not a functional language. However, the author brings up good points that transcend what language is being used for implementation. Also, since it is a book, it is more coherent than reading many papers on object-functional patterns. If you don't use Haskell in your day job (like me), then you might use a more conventional language like C#. If that is the case, then papers by Jeremy Gibbons will likely also be right up your alley (they will likely help you better communicate ideas to your coworkers). He has written a number of very readable papers about datatype generic programming. http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/ +1 to the idea of a book on patterns in a functional language. Cheers, Z-Bo

Stephen Tetley

22 Sep 22 Sep

6:42 a.m.

Hi Luc There is a catalogue of patterns for "strategic traversal" - Ralf Lammel (umlauts on the a in Lammel) and Joost Visser - "Design Patterns for Functional Strategic Programming". Strategic traversal is a "sub-field" of generic programming. http://homepages.cwi.nl/~ralf/dp-sf.pdf This was very valuable work, at the time Strafunski had various research papers but no manual as such. Without the pattern catalogue, one had to work through the manual for Stratego - the programming language that inspired Strafunski - and transliterate to Haskell. This was very difficult - Stratego is untyped, Strafuski used cutting edge features of Haskell's type system. It is a pity that there aren't more pattern catalogues for functional programming idioms. The functionals (maps, folds unfolds) and the monads could definitely be documented as design patterns, but there is lot of further ground that merits coverage - e.g. it would be nice if something captured good uses of existential types as design patterns. A book on program *design* focused on Haskell or other functional languages is very much missing, hopefully Richard Bird's new book will go some way towards this (although I think the book aims at something rather different - developing elegant algorithms - "pearls", rather than program design per se). Best wishes Stephen

Andrew Coppin

23 Sep 23 Sep

4:57 p.m.

On 22/09/2010 09:14 AM, Luc TAESCH wrote:

...

in real life I am doing architecture (appication and system) and I tend to see things differently with my haskell background. when reading what system XYZ does, I see folds, maps, lazy sort, memoisation , monads, etc...ie my mind apply idioms learned at code design level to architecture level

It's interesting to hear you say that. I've heard more than one person assert that "Haskell will never be popular", because "people don't think functionally". Or, more precisely, "people don't think recursively". It is asserted as fact that "people think imperatively". If you think that sounds silly, ask some random person (not a computer programmer, just some random human) how find the sum of a list of numbers. I can practically guarantee that most humans will reply "do X, then do Y, and then do Z". Almost nobody will reply with "the sum of an empty list is defined as zero, and the sum of a non-empty list is defined as the addition of the first element and the sum of the remaining elements". To a normal human, that almost sounds like a riddle rather than an explanation. Then again, who said that programmers had to be normal humans, or that programming had to be easy? Nobody seriously expects everyone to be able to dance or play pipe organ, so why should it be trivial for everybody to be able to program computers? (Of course, software giants make more money out of the "we make computers EASY!" slogan...)

Dan Piponi

7:13 p.m.

On Thu, Sep 23, 2010 at 1:57 PM, Andrew Coppin wrote:

...

If you think that sounds silly, ask some random person (not a computer programmer, just some random human) how find the sum of a list of numbers. I can practically guarantee that most humans will reply "do X, then do Y, and then do Z". Almost nobody will reply with "the sum of an empty list is defined as zero, and the sum of a non-empty list is defined as the addition of the first element and the sum of the remaining elements". To a normal human, that almost sounds like a riddle rather than an explanation.

I don't think it's unusual for a "random person" to give a recursive answer. It's just that a "normal human" tends to avoid anything that isn't tail recursion. For example, I can easily imagine someone saying "to sum a list, add the current element to the running total, and now carry on summing from the next element". I doubt most people would consider that to be a riddle. The problem is that humans don't have deep stacks, so they find it harder to talk in terms of methods that require deep stacks. -- Dan

Albert Y. C. Lai

24 Sep 24 Sep

5:02 p.m.

On 10-09-23 04:57 PM, Andrew Coppin wrote:

...

If you think that sounds silly, ask some random person (not a computer programmer, just some random human) how find the sum of a list of numbers.

My reply: to sum 10 numbers, sum 9 numbers, then account for the 10th. More at: http://groups.google.com/group/comp.lang.functional/msg/51df24fbf33b7059 Ask some random person how to find page 314 in a book. No one replies "check the 1st page, check the 2nd page, check the 3rd page...". In fact, no one replies in words. Almost everyone shows you how to cut to the middle or the estimated weighted middle (if the book seems to have 1000 pages, they cut near the one-third point), then say "oh, before this" or "oh, after this", repeat. Almost everyone divides and conquers. Almost everyone recurses. I am not a computer programmer. (I know that someone is bound to think, "when confronted with the problem of summing numbers, some people think, 'I know, I will divide and conquer'. Now they have two problems of summing numbers.")

Vo Minh Thu

6:24 p.m.

2010/9/24 Albert Y. C. Lai :

...

On 10-09-23 04:57 PM, Andrew Coppin wrote:

...
If you think that sounds silly, ask some random person (not a computer programmer, just some random human) how find the sum of a list of numbers.

My reply: to sum 10 numbers, sum 9 numbers, then account for the 10th. More at: http://groups.google.com/group/comp.lang.functional/msg/51df24fbf33b7059

Ask some random person how to find page 314 in a book. No one replies "check the 1st page, check the 2nd page, check the 3rd page...". In fact, no one replies in words. Almost everyone shows you how to cut to the middle or the estimated weighted middle (if the book seems to have 1000 pages, they cut near the one-third point), then say "oh, before this" or "oh, after this", repeat. Almost everyone divides and conquers. Almost everyone recurses.

I am not a computer programmer.

(I know that someone is bound to think, "when confronted with the problem of summing numbers, some people think, 'I know, I will divide and conquer'. Now they have two problems of summing numbers.")

A computer scientist knows how to count the stars in the sky: simply count half of them then multiply by two. -- or something like that.

aditya siram

26 Sep 26 Sep

2:48 p.m.

I haven't read this thread completely, but if someone else hasn't beaten me to it, there are *lots* of Haskell idioms spelled out on the Haskell Wiki [1] cleverly hidden under the category "Style". -deech [1] http://www.haskell.org/haskellwiki/Category:Style On Fri, Sep 24, 2010 at 5:24 PM, Vo Minh Thu wrote:

...

2010/9/24 Albert Y. C. Lai :

...
On 10-09-23 04:57 PM, Andrew Coppin wrote:

...
If you think that sounds silly, ask some random person (not a computer programmer, just some random human) how find the sum of a list of numbers.

My reply: to sum 10 numbers, sum 9 numbers, then account for the 10th. More at: http://groups.google.com/group/comp.lang.functional/msg/51df24fbf33b7059

Ask some random person how to find page 314 in a book. No one replies "check the 1st page, check the 2nd page, check the 3rd page...". In fact, no one replies in words. Almost everyone shows you how to cut to the middle or the estimated weighted middle (if the book seems to have 1000 pages, they cut near the one-third point), then say "oh, before this" or "oh, after this", repeat. Almost everyone divides and conquers. Almost everyone recurses.

I am not a computer programmer.

(I know that someone is bound to think, "when confronted with the problem of summing numbers, some people think, 'I know, I will divide and conquer'. Now they have two problems of summing numbers.")

A computer scientist knows how to count the stars in the sky: simply count half of them then multiply by two. -- or something like that. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

5351

Age (days ago)

5355

Last active (days ago)

List overview

Download

12 comments

12 participants

participants (12)

aditya siram
ajb＠spamcop.net
Albert Y. C. Lai
Andrew Coppin
Dan Piponi
Jason Dagit
Jim Snow
Johannes Waldmann
John Zabroski
Luc TAESCH
Stephen Tetley
Vo Minh Thu