Boost logo

Boost :

From: Pavol Droba (droba_at_[hidden])
Date: 2003-10-24 10:02:32


On Thu, Oct 23, 2003 at 11:21:54PM -0400, David Abrahams wrote:
> Pavol Droba <droba_at_[hidden]> writes:

[snip]
 
> >> ?? We're not talking about making a copy, since the result differs
> >> from the input. In general, you pay the same price in functional
> >> languages.
> >>
> >
> > So there is realy NO copy performed in Haskell when evaluating the function,
> > it is a transformation. And this is much closer to inplace version,
> > in C++ then to copy one.
>
> Gimme a break, man! In pure FP languages data is immutable, so
> there's no way to make inplace changes. In Haskell you have to go
> into a monad to escape this restriction.
>

I know that this discusion is out of topic, quite a bit, but here is my
explanation what I mean, when I say, that nothing is copied:

Most of modern FP languages, perform the execution in terms of graph-reduction machine.
High level syntax is precompiled to a extended version of lambda calculus
and this is then executed.

State of an execution is represented by a term, which is represented by a graph.
This graph is being reduced as the lambda calculi reduction rules are
applied.

There is nothing like a stack or variables in this representation. So unless
some subterm is bound to more then one expression, it can be safetly modified
in-place. And thats usualy what is being done.

For better explanation here is an example.

lets have a function "f : string->string" and a string, whatever its representation is.
lets have a term:

(trim str1)

this term is represented by a term representation of trim (subgraph), str1 node and "apply" node.

In the first step, "apply" node is reduced. This means, that an empty pointer in trim
subgraph, representing an argument, is pointed to str1.
In the further steps, trim will be reduced, but the reduction will be performed
directly on str1. It will not be copied, because it is not necessary.

> > In copy variant, we are actualy making a copy of the input. That is
> > the actualy the difference between copy and inplace variant.
>
> If you are implementing trim by first copying the entire input and
> then modifying it to trim off the parts you don't want, you really
> are doing it very inefficiently... especially if most or all of the
> input must be trimmed.
>

Definitely not, but a new container has to be allocated and result
is stored there. The result is actualy a copy of input with a transformation
applied. Therefore I'm refering to it as a copy.
 

[snip]

> > And the last words for this topic. Given the fact, that this
> > particular issue is realy only a matter of personal preference,
>
> It is not *only* a matter of personal preference. I think there are
> some ways in which the functional approach is objectively safer, as I
> demonstrated with my example. It is, however, mostly personal
> preference.
>

Ok :)

Regards,

Pavol


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk