Warp wrote:
>   It would be less efficient because it would require always deep-copying
> data when it's passed around?

Basically. Deep-copying and duplicating.

If I say
   X is a list [1, 2, 3]
   Y is a list prepending 0 to X
   Z is a list prepending 9 to X
then X is still out there only once, and Y and Z point to it. Lists are 
"linked lists" rather than array-like lists.

>> The real situation is of course a bit more complicated than this, but 
>> you get the idea.
> 
>   It looks like a really inefficient way of computing a simple calculation.

It's a lazy calculation. Hopefully the compiler can figure out when it 
doesn't actually need to do that.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

On 11/11/2010 12:38 PM, Darren New wrote:
>
> It's a lazy calculation. Hopefully the compiler can figure out when it
> doesn't actually need to do that.
>

However, as I understand it (keeping in mind that I don't actually know 
Haskell) it does have the implication that it can be much harder to 
reason about the efficiency of a program, since it depends quite a bit 
on what tricks the compiler can use.  This is in contrast to a language 
like C where the relative simplicity of the compiler means that the 
approximate performance is much more obvious.

It seems like a pretty common double-edged sword.  Smarter systems often 
allow you to do things more easily at the cost of the need for more 
mental space required to know when the smart system will fail and how to 
correct it.

Post a reply to this message

Kevin Wampler wrote:
> It seems like a pretty common double-edged sword. 

Yep.

> Smarter systems often 
> allow you to do things more easily at the cost of the need for more 
> mental space required to know when the smart system will fail and how to 
> correct it.

I think the best model is something SQL-like. Where you express the 
semantics of what you want, and then in a separate place say "by the way, 
here's hints to make it faster."

It's also the case that, generally speaking, there are on occasion things 
you can make more efficient in a higher-level language than a lower-level 
language, simply because there's more information about intent there. As in, 
it's way easier for C to micro-optimize my call to memcpy() than it is to 
micro-optimize my while loop that does semantically the same thing. And it's 
way easier for the SQL interpreter to figure out the best access pattern 
than it is for my C compiler to analyze my code along with the BDM to figure 
out how to optimize access.

Unfortunately, there are relatively few high-level languages that actually 
give you the option of telling the system how best to optimize stuff, even 
tho the concept has been around for ages.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

On 11/11/2010 05:19 PM, Warp wrote:
> Invisible<voi### [at] devnull>  wrote:
>> I always used to think that creating a data structure who's size is not
>> statically known required handling it by reference. However, C++ somehow
>> manages to do this by value, so it seems my assumptions are incorrect.
>
>    No, dynamically allocated objects can only be handled with a pointer.
> You can of course wrap that pointer so that it looks and behaves like
> the allocated object itself, but as if handled by-value (including being
> scope-bound).
>
>    For example you can handle an instance of std::vector or std::string
> by value, but internally they contain a pointer to dynamically allocated
> memory (which they manage).

I see. (I think!) So, presumably, when you copy std::vector "by value", 
all it's actually copying is the reference to the real data?

>> In fact, thinking about it, you probably /could/ implement Haskell
>> without GC. It would just be far less efficient, that's all.
>
>    It would be less efficient because it would require always deep-copying
> data when it's passed around?

That's one reason.

The other reason is that Haskell expressions are not restricted to being 
*trees*. They can be general *graphs*. This is how you implement a 
common sub-expression such that it only gets computed once - a very 
useful thing to be able to do (obviously). I'm not quite sure how this 
would interact with a non-GC implementation.

>> The real situation is of course a bit more complicated than this, but
>> you get the idea.
>
>    It looks like a really inefficient way of computing a simple calculation.

It is. That's why there's an entire optimiser pass dedicated to removing 
all these steps if possible. If a, b and x are just plain ordinary 
integers, it's highly likely that the final machine code will just chuck 
those variables into machine registers and do the usual binary 
arithmetic directly.

Of course, all of this graph reduction /is/ pointless for a simple piece 
of arithmetic. But if we choose a less trivial example, it becomes clear 
why it's useful. For example, that old chestnut of the Fibonacci 
function where the output depends on the output. That's impossible in a 
normal language, but trivial in Haskell.

(Obviously no programmer in history has actually /needed/ the Fibonacci 
numbers. And if they did, there's a well-known O(1) algorithm for them 
anyway. It's just an example.)

Post a reply to this message

> ...and now I'm reading about Agda, a programming language which has
> MELTED MY MIND! >_<

Idris is similar, with moderately less mind-meltation. Even so, all of 
the documentation is clearly written for somebody already familiar with 
the idea and just wanting to learn the actual syntax.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> >   It looks like a really inefficient way of computing a simple calculation.

> It's a lazy calculation. Hopefully the compiler can figure out when it 
> doesn't actually need to do that.

  It's provable (no, not a typo of "probable", different thing) that, in
the general case, the problem "will this line of code ever be executed?"
is an unsolvable problem. Hence a compiler can make that decision only
in the most trivial cases.

-- 
                                                          - Warp

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> I see. (I think!) So, presumably, when you copy std::vector "by value", 
> all it's actually copying is the reference to the real data?

  Actually, when you assign an std::vector object to another, whether it
performs a deep-copy of the data or if it uses some copy-on-write mechanism
to perform lazy copying depends on the library implementation, but AFAIK
most if not all library implementations use deep-copying.

  Thus, if you assign one std::vector object to another, all the data it
contains will be copied as well.

  Of course if you want copy-on-write instead, then you can create your own
"vector" which does that. (I have actually done precisely this for some
projects because of the benefits of this technique.)

-- 
                                                          - Warp

Post a reply to this message

>> It's a lazy calculation. Hopefully the compiler can figure out when it
>> doesn't actually need to do that.
>
>    It's provable (no, not a typo of "probable", different thing) that, in
> the general case, the problem "will this line of code ever be executed?"
> is an unsolvable problem. Hence a compiler can make that decision only
> in the most trivial cases.

More tractable is "if X is executed then Y is definitely executed". For 
example, the arguments to (+) [over integers] will always be executed. 
Therefore, any code that calls (+) can just pass two integers, rather 
than bothering to build a graph of heap objects to pass.

It would be one thing if the compiler knew about the special properties 
of built-in functions like (+). But in fact it performs a "strictness 
analysis" pass which infers this information for all user-written code.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message