Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Oliver Bandel]

On Tue, Oct 04, 2005 at 07:45:12PM -0500, Brian Hurt wrote:
[...] 
> The big advantage of FP programming IMHO is not performance, but instead 
> *correctness*.  With today's multi-gigahertz machines with multi-gigabytes 
> of memory, performance isn't as critical as it used to be.  But 
> correctness- especially automatically gaurenteed correctness on projects 
> spanning hundreds of thousands of lines of code and dozens of developers 
> maintained over decades of time- starts becoming critical.

Yes, I agree on this.
I get daily messages from an buglist-mailinglist, where most often
things like typical memory-exploits are the reason of why a system
or a process can be exploited.

So, the typical "out of bounds" and "format string" problems
are typical security risks.
(Btw: is OCaml's format-string stuff from the Printf-module save in
this respect?!)


> I'd quite 
> happily trade off 10% performance for correctness, or even 50% 
> performance.

Well, if the code with correctness is nearly as fast as the code without,
it would be best.


> 
> FP is a huge gain in correctness, because it allows me to *control 
> mutability*.  If I pass a mutable data structure to a block of code there 
> is an instant implicit contract between the caller and the callee on how 
> (or wether) to modify the mutable data structure.  It doesn't matter what 
> the contract is- wether it's to not modify the structure at all, to allow 
> optional modification (either unlimited or only in certain ways), or to 
> require certain modifications- a dependency between the two different 
> peices of code exists.  And this dependency, this contract, is probably 
> undocumented and always unchecked by the compiler, which means it's a 
> maintaince nightmare waiting to happen.  One peice of code gets modified 
> to violate the contract, perhaps even unknowingly, or perhaps due to some 
> changing requirement, and untouched code thousands of lines away suddenly 
> breaks.


Yes, this is a very well description of the FP-advantages.
Nevertheless, if a solution is too slow, it hinders
people from adopting FPLs for their programmig, and
software remains unsecure/unsafe, because they again and again
will choose the unsafe langauges... :(


Ciao,
   Oliver

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[William Lovas]

On Wed, Oct 05, 2005 at 03:45:52PM +0200, Oliver Bandel wrote:
> So, the typical "out of bounds" and "format string" problems
> are typical security risks.
> (Btw: is OCaml's format-string stuff from the Printf-module save in
> this respect?!)

As far as i understand the "format string" bugs, they arise when a
programmer writes a call to printf whose first argument comes from
user input.  In O'Caml the various *printf functions require their
first argument to have type "('a, 'b, 'c) format", for some values
of 'a, 'b, and 'c.  As far as i can tell there's no way to produce
a value of this type from user input, so O'Caml should be safe.

In fact, there might even be a better reason O'Caml is safe, like
that it doesn't automatically keep looking for arguments until it
runs out of %expandos, but rather it just produces a closure that
can be applied to more arguments later.  But this is just a guess,
based on a quick 5-minute perusal of the O'Caml standard library.

cheers,
William

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[skaller]

On Wed, 2005-10-05 at 14:10 +0200, Oliver Bandel wrote:

> For example, I'm not really a fan of OO-programming, but when
> programming GUI-software I think it would be the best choice,
> and FP-programming lacks flexibility here 

I contend that concurrent programming is best here.
However, I don't know: I have a tool (Felix) to explore
this, but haven't got around to actually trying the
one-thread/one-widget paradigm. 

The OO solution is reactive and requires you to maintain
the whole widget state without use of the stack, thereby
discarding everything that is known about block structured
and functional programming, and going back to the bad old
days of the early 70s with a flat state space, except that
the state space is partitioned into objects.

The thread based solution control inverts this paradigm,
giving you a stack and control flow for every widget,
this is *active* or algorithmic programming. So I content
it must be better, because it not only partitions the state
space as OO does, it *also* partitions the control space,
and allows you to use all the advantages of a functional
or block structured style.

Actually, in practice, I expect a mix of the solutions
will be best. The reason is: we know a LOT about
state machines. So subparts of problems which correspond
to them can easily be programmed and reasoned about,
simply because we have lots of mature theory.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Jon Harrop]

On Wednesday 05 October 2005 13:10, Oliver Bandel wrote:
> For example, I'm not really a fan of OO-programming, but when
> programming GUI-software I think it would be the best choice,
> and FP-programming lacks flexibility here (if not using
> a DSL to create GUI-code, which then is separately compiled).

I am finding ordinary FP perfectly adequate for GUI programming. My GUI 
programming may be unorthodox, however. :-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Oliver Bandel]

On Tue, Oct 04, 2005 at 06:39:28PM -0400, Christopher A. Watford wrote:
[...] 
> This list is best for asking OCaml questions and is awful for asking
> for what language is best for what, nobody agrees.
[...] 


I was not asking, what language is better for soimething, or best at all.
I asked for what programming style/paradigm is best used to solve
certain problems.

As OCaml provides more than one programming paradigm, for me
it's the best language I ever had programmed in (some
other features are also fine).

So the question goes in a different direction:
  How to solve problems best, if you have the possibility
  do do it in different ways.

Well, every programmer can choose it's own way, but if certain areas
are well known to do them in a certain way best, it  makes sense
to go that direction.

For example, I'm not really a fan of OO-programming, but when
programming GUI-software I think it would be the best choice,
and FP-programming lacks flexibility here (if not using
a DSL to create GUI-code, which then is separately compiled).

Ciao,
   Oliver

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Brian Hurt]

On Tue, 4 Oct 2005, Oliver Bandel wrote:

> Most often people say, imperative is faster in most of all
> cases, and only in some cases FP might be faster.

The general argument here is that if the FP solution is faster, the 
imperitive language can just implement the FP solution.  My answer to that 
is that imperitive programming languages discourage you from thinking in 
certain ways rather strongly- while the FP solution may be faster, it's 
not "natural".

The big advantage of FP programming IMHO is not performance, but instead 
*correctness*.  With today's multi-gigahertz machines with multi-gigabytes 
of memory, performance isn't as critical as it used to be.  But 
correctness- especially automatically gaurenteed correctness on projects 
spanning hundreds of thousands of lines of code and dozens of developers 
maintained over decades of time- starts becoming critical.  I'd quite 
happily trade off 10% performance for correctness, or even 50% 
performance.

FP is a huge gain in correctness, because it allows me to *control 
mutability*.  If I pass a mutable data structure to a block of code there 
is an instant implicit contract between the caller and the callee on how 
(or wether) to modify the mutable data structure.  It doesn't matter what 
the contract is- wether it's to not modify the structure at all, to allow 
optional modification (either unlimited or only in certain ways), or to 
require certain modifications- a dependency between the two different 
peices of code exists.  And this dependency, this contract, is probably 
undocumented and always unchecked by the compiler, which means it's a 
maintaince nightmare waiting to happen.  One peice of code gets modified 
to violate the contract, perhaps even unknowingly, or perhaps due to some 
changing requirement, and untouched code thousands of lines away suddenly 
breaks.

Note that such a bidirectional dependency can be implemented in functional 
code- the called code returns a new copy of the modified structure to the 
calling code, which the calling code then adopts and uses.  But notice 
that such a bidirectional dependency is explicitly stated in the code, and 
automatically checked by the compiler.  And the calling code has the 
option of wether or not to allow the modification (or to use both the old 
and the new copy).

Java programmers are begining to tumble to this advantage- notice the 
increasing popularity of immutable objects (starting with Int and Float), 
and Java Beans.

> I recently had a discussion about some OO-patterns
> ( so called "GoF"-Book) and tried to solve some of them with
> OCamls module system.
> Adapter and bridge was talked about. Adapter was easy in writing a simple
> wrapper.
> Bridge could be done with a functor. :)

Some of the patterns are doable with modules.  Singleton, for example, is 
a classic module pattern.  Many of the patterns aren't, however.  An 
important comment here is that modules are NOT weird and broken objects. 
A better point of comparison is C++ templates, except that 95+% of the use 
of templates in C++ is to implement universal types, i.e. a C++ programmer 
writes "list<A>" where an Ocaml programmer would write "'a list".

>
> Another interesting theme in this respect is: If not only some patterns
> were adapted to Fp, but the whole problem solving approach is different,
> which patterns will be unnevcessary then, because the whole structure of
> the software will be different...?!

There are patterns in every programming idiom.  The GoF book was just 
Object Oriented patterns- but there are procedural patterns, and 
functional patterns, and logic patterns, etc.

Brian

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Jon Harrop]

On Tuesday 04 October 2005 23:38, Michael Wohlwend wrote:
> there is a paper "Design Patterns in OCaml"  which describes various
> patterns:
> http://people.csail.mit.edu/dnj/teaching/6898/projects/vicente-wagner.pdf

I think I read this paper some time ago but it was interesting to read it 
again. Firstly, it gives only 3 references, doesn't appear to be complete, I 
think it is out of date and it appears to be written from the point of view 
of a dynamic typer. Secondly, I was never a fan of "design patterns".

As they say, several "design patterns" have trivial counterparts in FPLs, 
roughly: Singleton = module structure, Facade = module signature, Command = 
currying, Memento = dynamic type checking, and Strategy = HOFs.

The paper repeatedly states that modules cannot be mutually recursive. AFAIK, 
this has not been true for some time.

In the section about the "Observer" pattern, they state "a meaningless method 
call must be inserted into the code because OCaml's static checker cannot 
infer the type of the ...". Can the meaningless method not be replaced with a 
type declaration?

Perhaps the "State" pattern can be better represented by reusing polymorphic 
variants.

Overall, I'd say that the idea of design patterns is reasonable but the GOFs 
work is not relevant to OCaml - the study will need to be redone from 
scratch. I am much more interested in the automation of the factoring of code 
patterns, although I've yet to actually study it...

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Jon Harrop]

On Tuesday 04 October 2005 23:39, Christopher A. Watford wrote:
> This list is best for asking OCaml questions and is awful for asking
> for what language is best for what, nobody agrees.

Oliver was asking which of three programming paradigms is best under different 
circumstances. OCaml provides all three so I think this can be taken as an 
OCaml-specific question and is fine for this list.

I for one would be very interested in reading information on this. I'll check 
out the design patterns paper - thanks Michael.

My impression is that:

1. Data structure heavy code is often easier to write in a functional style. 
See the "n"th-nearest neighbour example from my book:

  http://www.ffconsultancy.com/products/ocaml_for_scientists/complete/

2. GUI code is more easily written with a stateful imperative front and often 
a functional back end.

I have yet to really exploit OCaml's OO capabilities.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Christopher A. Watford]

On 10/4/05, Oliver Bandel <oliver@first.in-berlin.de> wrote:
> Hello,
>
> is there a general overvie (paper or book), where
> functional and imperative approaches to solve a problem are
> compared directly?
>
> Most often people say, imperative is faster in most of all
> cases, and only in some cases FP might be faster.
>
> If there is a paper/book about problem solving and performance,
> comparing different approaches I would be happy to have a pointer
> to it.
>
> Also it would be nice to find something about how
> classical imperative style, OO-style and FP-style
> are solving problems, and which patterns can be done
> easier in the one or the other way.
>
> I recently had a discussion about some OO-patterns
> ( so called "GoF"-Book) and tried to solve some of them with
> OCamls module system.
> Adapter and bridge was talked about. Adapter was easy in writing a simple
> wrapper.
> Bridge could be done with a functor. :)
>
> So, if there are direct translations possible, where to find
> comparisons?
>
> Another interesting theme in this respect is: If not only some patterns
> were adapted to Fp, but the whole problem solving approach is different,
> which patterns will be unnevcessary then, because the whole structure of
> the software will be different...?!
>
> Ciao,
>   Oliver

Sigh, your question only begs for trolls to pop out of the corners.

It would probably be best to keep these questions off this list. Far
too often they go off into the deep end of the 'my language is better
than your language' debates. Obviously members of this list are going
to be biased towards functional languages and will probably give you
biased articles to read or biased papers. Not necessarily biased in a
bad way, just more likely to show functional languages in a good
light.

A poor place to start reading on the subject of what language is best
is The Computer Language Shootout [1]. An even worse place to start
reading is this list.

The actual performance for any program will depend largely on your
ability to program well for the language and for the specific compiler
you choose.

I would say it's obvious that some patterns are easier to *write* in a
certain language, but that hardly shows which language is *best* speed
wise. Your example shows one pattern functional languages are well
suited for, however, I'm sure an experienced C programmer could show
you an example of that pattern which is both efficient and easy to
read (I know I know people on this list may disagree).

This list is best for asking OCaml questions and is awful for asking
for what language is best for what, nobody agrees.

--
Christopher A. Watford
christopher.watford@gmail.com

[1] http://shootout.alioth.debian.org/

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Michael Wohlwend]

On Tuesday 04 October 2005 18:47, Oliver Bandel wrote:
>
> So, if there are direct translations possible, where to find
> comparisons?
>

there is a paper "Design Patterns in OCaml"  which describes various patterns:
http://people.csail.mit.edu/dnj/teaching/6898/projects/vicente-wagner.pdf

cheers,
 Michael

FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Oliver Bandel]

Hello,


is there a general overvie (paper or book), where
functional and imperative approaches to solve a problem are
compared directly?

Most often people say, imperative is faster in most of all
cases, and only in some cases FP might be faster.

If there is a paper/book about problem solving and performance,
comparing different approaches I would be happy to have a pointer
to it.

Also it would be nice to find something about how
classical imperative style, OO-style and FP-style
are solving problems, and which patterns can be done
easier in the one or the other way.

I recently had a discussion about some OO-patterns
( so called "GoF"-Book) and tried to solve some of them with
OCamls module system.
Adapter and bridge was talked about. Adapter was easy in writing a simple
wrapper.
Bridge could be done with a functor. :)


So, if there are direct translations possible, where to find
comparisons?

Another interesting theme in this respect is: If not only some patterns
were adapted to Fp, but the whole problem solving approach is different,
which patterns will be unnevcessary then, because the whole structure of
the software will be different...?!



Ciao,
   Oliver