# Design Patterns and Functional programming - Theory and Concepts

This is a discussion on Design Patterns and Functional programming - Theory and Concepts ; Daniel T. wrote: &gt; I'm downloading and building OCaml now, in the mean time... &gt; How about an alarm clock example? Or simply a program that prints a '.' &gt; on the screen every second? &gt; &gt; How are such ...

1. ## Re: Design Patterns and Functional programming

Daniel T. wrote:
> How about an alarm clock example? Or simply a program that prints a '.'
> on the screen every second?
>
> How are such things done in a stateless environment?

Take your last example. You can implement it statefully in OCaml using a
mutable reference:

# let clock () =
let ot = ref (int_of_float(Unix.gettimeofday())) in
while true do
let t = int_of_float(Unix.gettimeofday()) in
Printf.printf "%s%!" (String.make (t - !ot) '.');
ot := t;
done;;
# clock ();;
.......

or statelessly as a recursive function that passes state to itself:

# let rec clock ot =
let t = int_of_float(Unix.gettimeofday()) in
Printf.printf "%s%!" (String.make (t - ot) '.');
clock t;;
val clock : int -> 'a = <fun>
# clock (int_of_float(Unix.gettimeofday()));;
.......

This recursive "clock" function accepts the last time it was invoked (as an
int "ot") and prints t-ot dots before recursing with "t" as the last time
it was invoked. The "String.make n c" makes a string of "n" characters "c".
The "%!" in the call to printf is a flush.

I find graphical programs very gratifying to write and great for teaching.
Have a look at our Smoke vector graphics library (there's a free edition):

http://www.ffconsultancy.com/product...or_graphics?co

It uses a purely functional scene graph so it is much easier to use than
alternatives like Windows Presentation Foundation. Moreover, it is vastly
faster (and written entirely in OCaml). :-)

--
Dr Jon D Harrop, Flying Frog Consultancy
The OCaml Journal
http://www.ffconsultancy.com/product...ournal/?usenet

2. ## Re: Design Patterns and Functional programming

Patrick May wrote:
> Many patterns are symptoms of a problem, not aspects of a solution.

Exactly. Perhaps design patterns were supposed to reflect language agnostic
repetitions in software design but most things that are currently touted as
design patterns simply reflect shortcomings in object orientated
programming.

The Model-View-Controller design pattern is one of the more language-
agnostic patterns but it is still inherently imperative so it does not
generalize to functional reactive GUI programming, for example.

--
Dr Jon D Harrop, Flying Frog Consultancy
The OCaml Journal
http://www.ffconsultancy.com/product...ournal/?usenet

3. ## Re: Design Patterns and Functional programming

Patrick May wrote:

> Peter Norvig noted almost 10 years ago that 16 of the 23 patterns
> in the GoF book are "invisible or simpler" in Lisp
> (http://norvig.com/design-patterns).

True, but irrelevant to the topic at hand.

> This suggests that, rather than
> existing independently of the solution domain, many design patterns
> are actually standardized workarounds for limitations in the language
> used for implementation.

True, but irrelevant to the topic at hand.

> Paul Graham touches on this in his essay "Revenge of the Nerds":

> "When I see patterns in my programs, I consider it a sign of
> trouble. The shape of a program should reflect only the problem
> it needs to solve. Any other regularity in the code is a sign,
> to me at least, that I'm using abstractions that aren't powerful
> enough -- often that I'm generating by hand the expansions of
> some macro that I need to write."

> I find this argument compelling. Many patterns are symptoms of a
> problem, not aspects of a solution.

True, but not relevant to the topic at hand.

Do you see a pattern emerging (and what that means by your statement
immediately above) ... :-)

The fact that for many of these "problems" , prevailing FP langs provide
better means (by several measures) to solve the problem than prevailing
OOP langs, does not mean that all OOP does here is "re-invent" what FP
does.

Each paradigm has material constraints within, which makes solution to one
problem worse than in another. That is why for all the significant
paradigms (FP, OO, logic, procedural etc) , not one has become the
all-conquering paradigm( *** ) . Quite right too.

Regards,
Steven Perryman

*** although I do believe that FP + type substitutability is close to

Regards,
Steven Perryman

4. ## Re: Design Patterns and Functional programming

On Sun, 08 Jul 2007 18:35:51 +0100, Jon Harrop wrote:

> Dmitry A. Kazakov wrote:
>>> How do you add that to the object oriented design?

>>
>> No problem actually. You first derive from abstract expression an abstract
>> infix operation (that is - two arguments one result) and then specialize
>> it to concrete operation.

>
> Could you post working code for that design, please?

It contains a complete sample for building parsing trees of Ada 95 infix
expressions with all bells and whistles.

>> BTW, in a real compiler you won't have them in the form you have proposed.

>
> Most compilers written in Standard ML, Haskell or OCaml use this form.
> Indeed, this carries through to machine code generation as the machine
> itself doesn't implement n-ary addition.

Yes, but you definitely wanted to fold constants in expressions like 1+a+2.

>
> Precedence is implemented the same way in the functional and OO styles. For
> programmatic construction, it is inherited from the use of infix operators.

But your idea was to map that onto some [functional] language constructs,
which apparently do not take care of.

[...]

> What would the equivalent be in an object oriented design?

Follow the link I have provided. The focus of the design was to avoid
hard-coded grammar. Therefore decomposition goes along different lines. It
is operations, arguments, sources and parsers. The approach is
table-driven, that is - lexical elements, like infix operations, their
precedence are defined dynamically. Static are only the classes of, like
operator, bracket, comma, ligature. This gives you the operation and
argument stack objects in a fully generic way.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

5. ## Re: Design Patterns and Functional programming

S Perryman wrote:
> Patrick May wrote:
>> Peter Norvig noted almost 10 years ago that 16 of the 23 patterns
>> in the GoF book are "invisible or simpler" in Lisp
>> (http://norvig.com/design-patterns).

>
> True, but irrelevant to the topic at hand.

On the contrary, Patrick's statements hit the nail on the head.

> Each paradigm has material constraints within, which makes solution to one
> problem worse than in another. That is why for all the significant
> paradigms (FP, OO, logic, procedural etc) , not one has become the
> all-conquering paradigm( *** ) . Quite right too.

OCaml programmers are free to choose between many different paradigms
including OOP and FP and they almost always choose FP over OOP.

Even in F#, where every advantage is given to OOP as the underlying
implementation (.NET) is fundamentally object oriented and optimized for
that style of programming, functional style often wins through.

--
Dr Jon D Harrop, Flying Frog Consultancy
The OCaml Journal
http://www.ffconsultancy.com/product...ournal/?usenet

6. ## Re: Design Patterns and Functional programming

Jon Harrop wrote:

> S Perryman wrote:

>>Patrick May wrote:

>>>Peter Norvig noted almost 10 years ago that 16 of the 23 patterns
>>>in the GoF book are "invisible or simpler" in Lisp
>>>(http://norvig.com/design-patterns).

>>True, but irrelevant to the topic at hand.

> On the contrary, Patrick's statements hit the nail on the head.

No, he hit *a* nail. Not *the* nail. Which is :

<quote>

Is there any literature describing how object-oriented design patterns
reinvent existing techniques like functional programming?

</quote>

>>Each paradigm has material constraints within, which makes solution to one
>>problem worse than in another. That is why for all the significant
>>paradigms (FP, OO, logic, procedural etc) , not one has become the
>>all-conquering paradigm( *** ) . Quite right too.

> OCaml programmers are free to choose between many different paradigms
> including OOP and FP and they almost always choose FP over OOP.

If you wish to troll about FP/OCaml vs OOP, feel free to do so.

If you wish (as per your original posting) to find literature describing
what you seek, no one here appears to be able to help you. I suspect that
no such literature exists (I could be wrong) .

Regards,
Steven Perryman

7. ## Re: Design Patterns and Functional programming

Dmitry A. Kazakov wrote:
> On Sun, 08 Jul 2007 18:35:51 +0100, Jon Harrop wrote:
>> Dmitry A. Kazakov wrote:
>>>> How do you add that to the object oriented design?
>>>
>>> No problem actually. You first derive from abstract expression an
>>> abstract infix operation (that is - two arguments one result) and then
>>> specialize it to concrete operation.

>>
>> Could you post working code for that design, please?

>
>
> It contains a complete sample for building parsing trees of Ada 95 infix
> expressions with all bells and whistles.

Note that my post that you were replying to was about a term rewriter rather
than a parser. Regardless, parsing is another interesting example. I
OCaml program:

open Camlp4.PreCast;;

let expr = Gram.Entry.mk "expr";;

EXTEND Gram
expr:
[ "sum" LEFTA
[ e1 = expr; "+"; e2 = expr -> e1 +. e2
| e1 = expr; "-"; e2 = expr -> e1 -. e2 ]
| "product" LEFTA
[ e1 = expr; "*"; e2 = expr -> e1 *. e2
| e1 = expr; "/"; e2 = expr -> e1 /. e2 ]
| "power" LEFTA
[ e1 = expr; "**"; e2 = expr -> e1 ** e2 ]
| "simple" NONA
[ n = INT -> float_of_string n
| x = FLOAT -> float_of_string x
| "("; e = expr; ")" -> e ] ];
END;;

let rec loop() =
Printf.printf "> %!";
let x = Gram.parse expr Loc.ghost (Stream.of_string (input_line stdin)) in
Printf.printf "= %f\n%!" x;
loop();;

let () = loop()

>>> BTW, in a real compiler you won't have them in the form you have
>>> proposed.

>>
>> Most compilers written in Standard ML, Haskell or OCaml use this form.
>> Indeed, this carries through to machine code generation as the machine
>> itself doesn't implement n-ary addition.

>
> Yes, but you definitely wanted to fold constants in expressions like
> 1+a+2.

You might want to do that. If you do, just sort by commuting and the
existing reduction rules will take care of constant folding. Something like
this:

| Add(Add(f, g), h) when g>h -> f +: h +: g
| Add(f, g) when f>g -> g +: f

>>
>> Precedence is implemented the same way in the functional and OO styles.
>> For programmatic construction, it is inherited from the use of infix
>> operators.

>
> But your idea was to map that onto some [functional] language constructs,
> which apparently do not take care of.
>
> [...]

If we're talking about parsers then the handling of precedence levels should
be clear from the above example.

>> What would the equivalent be in an object oriented design?

>
> Follow the link I have provided. The focus of the design was to avoid
> hard-coded grammar. Therefore decomposition goes along different lines. It
> is operations, arguments, sources and parsers. The approach is
> table-driven, that is - lexical elements, like infix operations, their
> precedence are defined dynamically. Static are only the classes of, like
> operator, bracket, comma, ligature. This gives you the operation and
> argument stack objects in a fully generic way.

Does that design have any advantages over the functional solution above?

I would still be interested to see an object oriented equivalent to the term
rewriter. :-)

--
Dr Jon D Harrop, Flying Frog Consultancy
The OCaml Journal
http://www.ffconsultancy.com/product...ournal/?usenet

8. ## Re: Design Patterns and Functional programming

S Perryman wrote:
> Jon Harrop wrote:
>> OCaml programmers are free to choose between many different paradigms
>> including OOP and FP and they almost always choose FP over OOP.

>
> If you wish to troll about FP/OCaml vs OOP, feel free to do so.

How can a statement about OOP in OCaml be construed as OCaml vs OOP?!

> If you wish (as per your original posting) to find literature describing
> what you seek, no one here appears to be able to help you. I suspect that
> no such literature exists (I could be wrong).

Peter Norvig's article that Patrick cited is an excellent example. Peter
discussed only dynamically typed functional languages like Lisp and I think
a lot more can be said in the context of statically typed functional
languages as they provide many (all?) of the type checking benefits of
statically typed OO languages.

--
Dr Jon D Harrop, Flying Frog Consultancy
The OCaml Journal
http://www.ffconsultancy.com/product...ournal/?usenet

9. ## Re: Design Patterns and Functional programming

S Perryman <q@q.net> writes:
[ . . . ]
> True, but not relevant to the topic at hand.

[ . . . ]
> True, but not relevant to the topic at hand.

[ . . . ]
> True, but not relevant to the topic at hand.
>
> Do you see a pattern emerging (and what that means by your statement
> immediately above) ... :-)

Yes, but it's not relevant to the topic at hand. ;-)

> The fact that for many of these "problems" , prevailing FP langs
> provide better means (by several measures) to solve the problem than
> prevailing OOP langs, does not mean that all OOP does here is
> "re-invent" what FP does.

I agree. I was just replying to Mr. Lehman's post regarding
patterns being part of the solution domain rather than the problem
domain.

Regards,

Patrick

------------------------------------------------------------------------
S P Engineering, Inc. | Large scale, mission-critical, distributed OO
| systems design and implementation.
pjm@spe.com | (C++, Java, Common Lisp, Jini, middleware, SOA)

10. ## Re: Design Patterns and Functional programming

In article <m2vecueonh.fsf@spe.com>, Patrick May <pjm@spe.com> wrote:

> "H. S. Lahman" <h.lahman@verizon.net> writes:
> > Responding to Harrop...
> >> Function object => Closure
> >> Factory => Curried function
> >> Singleton => Value
> >> Command => Variant
> >> Iterator => Fold/Zipper
> >> Chain of Responsibility => Event
> >> Inversion of Control => Continuation passing style

> >
> > As Perryman's response (and yours to him!) indicate, FPLs and OOPLs
> > both provide syntax that enable the implementation of design
> > patterns. My point was that the design patterns exist independently
> > of the solution paradigm.

>
> Peter Norvig noted almost 10 years ago that 16 of the 23 patterns
> in the GoF book are "invisible or simpler" in Lisp
> (http://norvig.com/design-patterns). This suggests that, rather than
> existing independently of the solution domain, many design patterns
> are actually standardized workarounds for limitations in the language
> used for implementation.

Actually the Lisp and Dylan he has used both have strong OO features
that mix functional and object-oriented programming.
There is some tradition in Lisp for 'Knowledge Representation',
so lots of different patterns have been expressed in Lisp
and libraries/languages on top. It has features that makes
some patterns easy to express or to extend the vocabulary
so that patterns can be expressed.

BUT!

The patterns in the GoF book were just a small beginning.
There are hundreds of patterns (-> Booch) and many are not
that easy to express as language construct in most languages.

Patterns that are easily expressible in a functional language
are quite different from those that are easily expressible
in an object-oriented language.

A lot of architectural thinking uses ideas from the world
we see. Object-oriented architecture has some strong relationship
to our ideas of the world. We see objects. We see that
objects have an identity. There is communication between
objects. We have categories for objects (chair, furniture,
four-legged-thing, ...). Patterns around these ideas
are more easily expressed in object-oriented languages.
The first object-oriented language was a simulation language
(Simula).
That a few of these patterns are somehow trivial to express
in some languages is not that important. There are lots of patterns that
are not that easy to express by built-in language features.
We need to extend the language to express those or we can
try to replicate these patterns by more complex use of
built-in language features.

A mathematician may have other ways to model things
she sees. She has a very different vocabulary. She may
use stochastic models, markov chains, functional
process models, algebras, theorems, ... This
vocabulary is not easily expressible in an object-oriented
language (there have been some attempts). Patterns
around these can be expressed, but it is not trivial.
It is a different way of thinking.

The pattern community has a strong relation to object-oriented
design. But I'd say the functional way of thinking has also
lots of different patterns - patterns that you can
find in mathematics or physics books for example.

>
> Paul Graham touches on this in his essay "Revenge of the Nerds":
>
> "When I see patterns in my programs, I consider it a sign of
> trouble. The shape of a program should reflect only the problem
> it needs to solve. Any other regularity in the code is a sign,
> to me at least, that I'm using abstractions that aren't powerful
> enough -- often that I'm generating by hand the expansions of
> some macro that I need to write."
>
>
> I find this argument compelling. Many patterns are symptoms of a
> problem, not aspects of a solution.
>
> Regards,
>
> Patrick
>
> ------------------------------------------------------------------------
> S P Engineering, Inc. | Large scale, mission-critical, distributed OO
> | systems design and implementation.
> pjm@spe.com | (C++, Java, Common Lisp, Jini, middleware, SOA)

--
http://lispm.dyndns.org