Design Patterns and Functional programming

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

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

Responding to Harrop...

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

They don't. Design patterns exist outside both functional and OO
development. The OO paradigm just makes expressing design patterns
easier because it already emphasizes problem space abstraction.

Since the OO and functional paradigms are fundamentally incompatible,
one would need a different representation of design to express design
patterns in a form that is unambiguously mappable to FPLs. At present
there does not seem to be a body of literature for functional
programming that provides the sort of design methodologies that the
OOA/D literature provides. Without an appropriate notation for design
consistent with the paradigm it becomes difficult to express notions
like design patterns.


*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl@pathfindermda.com
Pathfinder Solutions
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
"Model-Based Translation: The Next Step in Agile Development". Email
info@pathfindermda.com for your copy.
Pathfinder is hiring:
http://www.pathfindermda.com/about_us/careers_pos3.php.
(888)OOA-PATH

H.S., brace yourself. I was going to respond earlier as well; however,
the wording of Jon Harrop's question prompted me to view his history
of postings. Afterwards I decided against it because of what I found.
I think you may have just opened Pandora's box. This should be
interesting. :-)

H. S. Lahman wrote:
> Responding to Harrop...
>> Is there any literature describing how object-oriented design patterns
>> reinvent existing techniques like functional programming?
>
> They don't.

Here are some examples:

Function object => Closure
Factory => Curried function
Singleton => Value
Command => Variant
Iterator => Fold/Zipper
Chain of Responsibility => Event
Inversion of Control => Continuation passing style

Let me give you a concrete example as well. Here is a simple curried
higher-order function that computes the numerical derivative of "f" at "x"
written first in a functional style (OCaml code):

# let d f x =
let dx = sqrt epsilon_float in
(f(x +. dx) -. f(x -. dx)) /. (2. *. dx);;
val d : (float -> float) -> float -> float = <fun>

Given the function f(x) = x^3-x-1:

# let f x = x**3. -. x -. 1.;;
val f : float -> float = <fun>

The derivative function f'(x) is given by:

# let f' = d f;;
val f' : float -> float = <fun>

Its value f'(3) at x=3 is:

# f' 3.;;
- : float = 26.

and in object oriented style (C++ code):

#include <iostream>
#include <limits>
#include <cmath>

using namespace std;

numeric_limits<double> real;

struct F { virtual double operator()(double x) = 0; };

struct D : F {
F *f;
double dx;
D(F *g) : f(g), dx(sqrt(real.epsilon())) {}
virtual double operator()(double x) {
return ((*f)(x + dx) - (*f)(x - dx)) / (2 * dx);
}
};

struct F1 : F {
virtual double operator()(double x) { return x*x*x - x - 1; }
};

int main() {
F1 f1;
cout << "d f 3 = " << D(&f1)(3) << endl;
}

The class "D" represents the function "d". Higher-order translates into
parameterizing D over F. Currying translates into deriving D from F. The
result is a factory for creating derivative functions.

> Design patterns exist outside both functional and OO
> The OO paradigm just makes expressing design patterns easier because it
> already emphasizes problem space abstraction.

You mean design patterns try to solve the problems that object orientation
has with abstraction?

> Since the OO and functional paradigms are fundamentally incompatible,

Given that some languages provide both OO and FP paradigms and several
languages even compile functional programs into object oriented
intermediate representations (F# targetting .NET and Scala targetting the
JVM, for example), in what sense are these paradigms "incompatible"? Do you
mean "complementary"?

If you look closer at OCaml, for example, you'll see that its OO features
are largely obsoleted by its functional features. Rewriting the above
example in an object oriented style in OCaml:

# class type f = object
method f : float -> float
end;;
class type f = object method f : float -> float end
# class f1 : f = object
method f x = x**3. -. x -. 1.
end;;
class f1 : f
# class d(f : f) : f = object
val dx = sqrt epsilon_float
method f x = (f#f(x +. dx) -. f#f(x -. dx)) /. (2. *. dx)
end;;
class d : f -> f
# let f1' = new d(new f1);;
val f1' : d = <obj>
# f1'#f 3.;;
- : float = 26.

You can see that the object oriented approach requires twice as much code.
Although the design patterns quantify the workarounds for object
orientations problems with abstraction, they clearly do not compete with
the existing functional solution in this case (and most others). When given
the choice, you can understand why programmers choose not to use OOP and
design patterns here.

> one would need a different representation of design to express design
> patterns in a form that is unambiguously mappable to FPLs. At present
> there does not seem to be a body of literature for functional
> programming that provides the sort of design methodologies that the
> OOA/D literature provides.

Yes, there are certainly a lot more books discussing problems with
abstraction in the context of object orientation.

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

Jon Harrop <jon@ffconsultancy.com> wrote:
> H. S. Lahman wrote:
> > Jon Harrop <jon@ffconsultancy.com> wrote:

> > > Is there any literature describing how object-oriented design patterns
> > > reinvent existing techniques like functional programming?
> >
> > They don't.
>
> [example snipped]
>
> You can see that the object oriented approach requires twice as much code.

I'm intrigued. Now show an OO problem written in both paradigms. Say two
classes that satisfy LSP and use the two state charts below:

f()
+->[A]---------->[b]
| |
| x() |
+-----------------+


f() f()
+->[A]---------->[b]---------->[C]
| | |
| x() | |
+-----------------+-------------+


Say in C++ (since you seem to know it

class Interface {
public:
virtual void f() = 0;
virtual void x() = 0;
};

class ObjA : public Interface {
enum State { A, B } state;
public:
virtual void f() {
state = B;
}
virtual void x() {
state = A;
}
};

class ObjB : public Interface {
enum State { A, B, C } state;
public:
virtual void f() {
state = state == A ? B : C;
}
virtual void x() {
state = A;
}
};

One last comment:

>
> #include <iostream>
> #include <limits>
> #include <cmath>
>
> using namespace std;
>
> numeric_limits<double> real;
>
> struct F { virtual double operator()(double x) = 0; };
>
> struct D : F {
> F *f;
> double dx;
> D(F *g) : f(g), dx(sqrt(real.epsilon())) {}
> virtual double operator()(double x) {
> return ((*f)(x + dx) - (*f)(x - dx)) / (2 * dx);
> }
> };
>
> struct F1 : F {
> virtual double operator()(double x) { return x*x*x - x - 1; }
> };
>
> int main() {
> F1 f1;
> cout << "d f 3 = " << D(&f1)(3) << endl;
> }

Why not just write:

int main() {
cout << "d f 3 = 26";
}

It does the same thing after all and much faster.

Daniel T. wrote:
> class Interface {
> public:
> virtual void f() = 0;
> virtual void x() = 0;
> };
>
> class ObjA : public Interface {
> enum State { A, B } state;
> public:
> virtual void f() {
> state = B;
> }
> virtual void x() {
> state = A;
> }
> };
>
> class ObjB : public Interface {
> enum State { A, B, C } state;
> public:
> virtual void f() {
> state = state == A ? B : C;
> }
> virtual void x() {
> state = A;
> }
> };

A simple functional equivalent in OCaml is ~9 lines long:

# type t =
| ObjA of [`A | `B]
| ObjB of [`A | `B | `C];;
type t = ObjA of [ `A | `B ] | ObjB of [ `A | `B | `C ]
# let f = function
| ObjA (`A | `B) -> ObjA `B
| ObjB `A -> ObjB `B
| ObjB (`B | `C) -> ObjB `C;;
val f : t -> t = <fun>
# let x = function
| ObjA (`A | `B) -> ObjA `A
| ObjB (`A | `B | `C) -> ObjB `A;;
val x : t -> t = <fun>

You only need to extend this example slightly to glimpse more of the power
of the functional approach. Consider an abstract syntax tree:

struct Expr {
};

struct Int : public Expr {
int n;
Int(int m) : n(m) {}
};

struct Add : public Expr {
Expr *f, *g;
Add(Expr *f2, Expr *g2) : f(f2), g(g2) {}
};

struct Mul : public Expr {
Expr *f, *g;
Mul(Expr *f2, Expr *g2) : f(f2), g(g2) {}
};

This is equivalent to:

# type expr =
| Int of int
| Add of expr * expr
| Mul of expr * expr;;
type expr = Int of int | Add of expr * expr | Mul of expr * expr

Now consider adding infix operators to simplify symbolic expressions as they
are constructed. In the functional style:

# let rec ( +: ) f g = match f, g with
| Int n, Int m -> Int (n + m)
| Int 0, e | e, Int 0 -> e
| f, g -> Add(f, g);;
val ( +: ) : expr -> expr -> expr = <fun>
# let rec ( *: ) f g = match f, g with
| Int n, Int m -> Int (n * m)
| Int 0, e | e, Int 0 -> Int 0
| Int 1, e | e, Int 1 -> e
| f, g -> Mul(f, g);;
val ( *: ) : expr -> expr -> expr = <fun>

How do you add that to the object oriented design?

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

On Sun, 08 Jul 2007 04:28:17 +0100, Jon Harrop wrote:

> You only need to extend this example slightly to glimpse more of the power
> of the functional approach. Consider an abstract syntax tree:
>
> struct Expr {
> };
>
> struct Int : public Expr {
> int n;
> Int(int m) : n(m) {}
> };
>
> struct Add : public Expr {
> Expr *f, *g;
> Add(Expr *f2, Expr *g2) : f(f2), g(g2) {}
> };
>
> struct Mul : public Expr {
> Expr *f, *g;
> Mul(Expr *f2, Expr *g2) : f(f2), g(g2) {}
> };
>
> This is equivalent to:
>
> # type expr =
> | Int of int
> | Add of expr * expr
> | Mul of expr * expr;;
> type expr = Int of int | Add of expr * expr | Mul of expr * expr
>
> Now consider adding infix operators to simplify symbolic expressions as they
> are constructed. In the functional style:
>
> # let rec ( +: ) f g = match f, g with
> | Int n, Int m -> Int (n + m)
> | Int 0, e | e, Int 0 -> e
> | f, g -> Add(f, g);;
> val ( +: ) : expr -> expr -> expr = <fun>
> # let rec ( *: ) f g = match f, g with
> | Int n, Int m -> Int (n * m)
> | Int 0, e | e, Int 0 -> Int 0
> | Int 1, e | e, Int 1 -> e
> | f, g -> Mul(f, g);;
> val ( *: ) : expr -> expr -> expr = <fun>
>
> 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.

BTW, in a real compiler you won't have them in the form you have proposed.
Think about optimizations made later during code generation. You would
really wish to factorize infix commutative operators like a+b+c+d out into
Sum(a,b,c,d). The number of arguments becomes variable.

How do you add precedence to your design? Association order? Association
checks? [this is when x and y or z is illegal without brackets] What about
types and types matching? Reasonable error diagnostic and recovery? Array
aggregates? Literals? Function calls? Keyed parameter association?
Defaulted parameters? Extension aggregates?

Do you honestly believe that a syntax + semantic analyzer can be 100 lines
long? If not, then what about readability, maintainability, reuse etc?

Object-oriented only means that the tree and its nodes are considered
objects of some types.

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

Jon Harrop <jon@ffconsultancy.com> wrote:
> Daniel T. wrote:

> > class Interface {
> > public:
> > virtual void f() = 0;
> > virtual void x() = 0;
> > };
> >
> > class ObjA : public Interface {
> > enum State { A, B } state;
> > public:
> > virtual void f() {
> > state = B;
> > }
> > virtual void x() {
> > state = A;
> > }
> > };
> >
> > class ObjB : public Interface {
> > enum State { A, B, C } state;
> > public:
> > virtual void f() {
> > state = state == A ? B : C;
> > }
> > virtual void x() {
> > state = A;
> > }
> > };
>
> A simple functional equivalent in OCaml is ~9 lines long:

I'm not sure what you are calling "lines" here to say the example below
is "~9 lines long". The C++ version has only 4 executable lines... What
is the functional equivalent in Scheme?

> # type t =
> | ObjA of [`A | `B]
> | ObjB of [`A | `B | `C];;
> type t = ObjA of [ `A | `B ] | ObjB of [ `A | `B | `C ]
> # let f = function
> | ObjA (`A | `B) -> ObjA `B
> | ObjB `A -> ObjB `B
> | ObjB (`B | `C) -> ObjB `C;;
> val f : t -> t = <fun>
> # let x = function
> | ObjA (`A | `B) -> ObjA `A
> | ObjB (`A | `B | `C) -> ObjB `A;;
> val x : t -> t = <fun>
>
> You only need to extend this example slightly to glimpse more of the power
> of the functional approach. Consider an abstract syntax tree:
>
> struct Expr {
> };
>
> struct Int : public Expr {
> int n;
> Int(int m) : n(m) {}
> };
>
> struct Add : public Expr {
> Expr *f, *g;
> Add(Expr *f2, Expr *g2) : f(f2), g(g2) {}
> };
>
> struct Mul : public Expr {
> Expr *f, *g;
> Mul(Expr *f2, Expr *g2) : f(f2), g(g2) {}
> };
>
> This is equivalent to:
>
> # type expr =
> | Int of int
> | Add of expr * expr
> | Mul of expr * expr;;
> type expr = Int of int | Add of expr * expr | Mul of expr * expr
>
> Now consider adding infix operators to simplify symbolic expressions as they
> are constructed. In the functional style:
>
> # let rec ( +: ) f g = match f, g with
> | Int n, Int m -> Int (n + m)
> | Int 0, e | e, Int 0 -> e
> | f, g -> Add(f, g);;
> val ( +: ) : expr -> expr -> expr = <fun>
> # let rec ( *: ) f g = match f, g with
> | Int n, Int m -> Int (n * m)
> | Int 0, e | e, Int 0 -> Int 0
> | Int 1, e | e, Int 1 -> e
> | f, g -> Mul(f, g);;
> val ( *: ) : expr -> expr -> expr = <fun>
>
> How do you add that to the object oriented design?

I have no clue what the above does, so I can't say. I have been
intrigued by functional languages for many years, but I have been unable
to wrap my head around their apparently stateless nature. My programming
problems have always involved state machines reacting to each other and
the user through time.

Can you recommend some good tutorials? I would be interested in, for
example, how one would program pong in OCaml or any functional language.
What language do you recommend I start with?

Jon Harrop wrote:

> H. S. Lahman wrote:

>>Responding to Harrop...

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

>>They don't.

> Here are some examples:

> Function object => Closure

Not quite.

Often in OOP, the "function" objects (orderings etc) take all
parameters as arguments (ie some of the parameters are not already
bound to the function) .


> Factory => Curried function

Quite a stretch to make this statement fit the facts.

Factory objects are not constrained to have factory ops taking only
one input parameter (a requirement for "curried" ops) .

And to be honest, attempting to emulate an N parameter function in
curried form with a chain of factory object invocations makes the
brain bleed just thinking about it.


> Singleton => Value

Yeah, you can use Singleton to emulate the latter.
But the Singleton pattern did not emerge to solve this particular
problem.


> Command => Variant

Actually the Command pattern IMHO has a stronger relationship to
closures (specifically, the attempt to provide a homogeneous interface
to a set of behaviours that often have different input parameters) .


> Iterator => Fold/Zipper

The typical iterator used in OOP is state-based (advance, more etc) .

An OOP collection framework that provides ops that do 'something' to each
element in a collection etc are more akin to the classic map/reduce of FP
(and applicative programming) .


The summary is that certain OO patterns can be used to provide equivalents
of what would be done in FP by particular semantic constructs. But this is
not really a case of OOP trying to "re-invent" what has been established in
FP for some time.


Regards,
Steven Perryman

S Perryman wrote:
> Jon Harrop wrote:
>> Function object => Closure
>
> Not quite.
>
> Often in OOP, the "function" objects (orderings etc) take all
> parameters as arguments (ie some of the parameters are not already
> bound to the function) .

With a closure, the parameters are the free variables and these are captured
automatically for you.

>> Factory => Curried function
>
> Quite a stretch to make this statement fit the facts.
>
> Factory objects are not constrained to have factory ops taking only
> one input parameter (a requirement for "curried" ops) .

Neither is a curried function.

> And to be honest, attempting to emulate an N parameter function in
> curried form with a chain of factory object invocations makes the
> brain bleed just thinking about it.

This is actually the convention in OCaml.

>> Command => Variant
>
> Actually the Command pattern IMHO has a stronger relationship to
> closures (specifically, the attempt to provide a homogeneous interface
> to a set of behaviours that often have different input parameters) .

Ok.

>> Iterator => Fold/Zipper
>
> The typical iterator used in OOP is state-based (advance, more etc) .

That is equivalent.

> An OOP collection framework that provides ops that do 'something' to each
> element in a collection etc are more akin to the classic map/reduce of FP
> (and applicative programming) .

Yes.

> The summary is that certain OO patterns can be used to provide equivalents
> of what would be done in FP by particular semantic constructs. But this is
> not really a case of OOP trying to "re-invent" what has been established
> in FP for some time.

It certainly seems this way to me.

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