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

Printable View

- 07-06-2007, 10:48 AMApplication DevelopmentDesign 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

- 07-07-2007, 10:01 AMApplication DevelopmentRe: Design Patterns and Functional programming
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

- 07-07-2007, 10:48 AMApplication DevelopmentRe: Design Patterns and Functional programming
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. :-)

- 07-07-2007, 05:16 PMApplication DevelopmentRe: Design Patterns and Functional programming
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

- 07-07-2007, 07:47 PMApplication DevelopmentRe: Design Patterns and Functional programming
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.

- 07-07-2007, 10:28 PMApplication DevelopmentRe: Design Patterns and Functional programming
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

- 07-08-2007, 03:19 AMApplication DevelopmentRe: Design Patterns and Functional programming
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 ****yzer 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

- 07-08-2007, 08:43 AMApplication DevelopmentRe: Design Patterns and Functional programming
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?

- 07-08-2007, 08:53 AMApplication DevelopmentRe: Design Patterns and Functional programming
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

- 07-08-2007, 09:22 AMApplication DevelopmentRe: Design Patterns and Functional programming
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