 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> I thought Lisp separates everything with parentheses.
>
>> In Haskell, you say
>
>> abc def ghi
>
> Are those three commands or one command with two arguments?
That's the function "abc" with arguments "def" and "ghi". In more
typical syntax, you would write
abc(def, ghi)
>> In Lisp, you say
>
>> (abc def ghi)
>
> Because, AFAIK, that is the latter.
Indeed.
I suppose the major difference is that in Haskell, you can write
1 + 2
whereas in Lisp, you say
(+ 1 2)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>>> Then the old heap is in oldheap and the new heap is in newheap.
>>>
>>> Is this supposed to be efficient?
>
>> Modifying log N nodes of the old heap to construct the new one? I'd say
>> it's reasonably efficient, yes.
>
> Not modifying. *Copying*. There's a huge difference.
Not really. We're talking about 4 machine words. Modifying one of those
words would be faster than copying all 4 of them, but I doubt that the
speed difference is astronomical. I'm sure C++ passes bigger structs
than that by value all the time...
> (All in-place data
> containers and algorithms *modify* the elements, that's not the problem.
> The problem I see there with Haskell is that it *copies* the elements.)
>
> (Also: Imagine that the elements of the heap had some mutable data
> container in them. Of course that's not purely functional anymore, but
> AFAIK that's *possible* in Haskell. How can you avoid having to copy the
> entire tree when you insert or remove a node? It's not like the new heap
> and the old heap could share some of the nodes, because if you modify the
> mutable container of one of those nodes, the other heap is going to see
> the modification.)
I'm not really following what you're trying to say here.
If you're saying "immutable structures are inefficient", I'd have to say
that I'll take the vast increase in reliability, maintainability,
flexibility and so forth over a few percent performance hit.
If you're saying "if you put mutable data into an immutable container,
things can go wrong", I'd say don't do that. Unless you really clearly
understand the implications and there's some advantage to doing it this way.
I would like to point out that the whole /benefit/ of a min-heap is that
it provides O(1) access to the minimum element. Well, that's only
possible because of the heap invariant - i.e., because data is stored in
semi-sorted order. If you can mutate the elements, you can trivially
break that invariant.
If you implemented this in Java or Pascal, you'd write a note in the
documentation saying "please don't mutate the elements in a way that
changes their relative ordering". In Haskell, you can make it so people
/can't/ change the relative ordering.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] dev null> wrote:
> >>> I thought Lisp separates everything with parentheses.
> >
> >> In Haskell, you say
> >
> >> abc def ghi
> >
> > Are those three commands or one command with two arguments?
> That's the function "abc" with arguments "def" and "ghi". In more
> typical syntax, you would write
> abc(def, ghi)
So Lisp does use parentheses as separators.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 06/09/2011 04:57 PM, Warp wrote:
> Invisible<voi### [at] devnull> wrote:
>>>>> I thought Lisp separates everything with parentheses.
>>>
>>>> In Haskell, you say
>>>
>>>> abc def ghi
>>>
>>> Are those three commands or one command with two arguments?
>
>> That's the function "abc" with arguments "def" and "ghi". In more
>> typical syntax, you would write
>
>> abc(def, ghi)
>
> So Lisp does use parentheses as separators.
No, I'm saying that's what you'd write in C or Java or whatever. In Lisp
you'd say (abc def ghi), like I originally posted.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/6/2011 8:03, Warp wrote:
> Darren New<dne### [at] sanrrcom> wrote:
>> Then the old heap is in oldheap and the new heap is in newheap.
>
> Is this supposed to be efficient?
If your functional language is pure enough, your compiler can often optimize
out the apparent inefficiency. Of course, that requires a Sufficiently Smart
Compiler.
In practice, it's less efficient, but not as obviously awful as it would appear.
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> On 9/6/2011 8:03, Warp wrote:
> > Darren New<dne### [at] sanrrcom> wrote:
> >> Then the old heap is in oldheap and the new heap is in newheap.
> >
> > Is this supposed to be efficient?
> If your functional language is pure enough, your compiler can often optimize
> out the apparent inefficiency. Of course, that requires a Sufficiently Smart
> Compiler.
Hmm, for the compiler to be able to elide the copying and make the changes
in-place, it would have to know for sure that those nodes that are being
changed are not being referenced from anywhere else in the program. (Because,
obviously, if they are referenced by something else, that something else is
going to see the change although it shouldn't.)
I'm not sure how a compiler would be able to do that in a complex program
where nodes and containers are being passed around.
(Of course the copying is not a big deal if each node contains eg. a
couple of integers. However, it begins to matter if they contain for example
large strings, which isn't all that unusual.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/6/2011 13:28, Warp wrote:
> I'm not sure how a compiler would be able to do that in a complex program
> where nodes and containers are being passed around.
I don't know about Haskell, but in some of the other languages (like
Erlang), changes tend to be localized enough that you can do essentially a
full-program analysis. It also helps that nothing can point to a newer
object; that is, the old heap can never refer to the newer heap, because
that would require modifying things that already exist.
That said, I don't really understand the details of how such an analysis is
done myself.
> (Of course the copying is not a big deal if each node contains eg. a
> couple of integers. However, it begins to matter if they contain for example
> large strings, which isn't all that unusual.)
Sure. Or if it's storing a big structure that for whatever reason the
individual fields can't be shared, which would seem not unusual as well.
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> It also helps that nothing can point to a newer
> object; that is, the old heap can never refer to the newer heap, because
> that would require modifying things that already exist.
That's true if the nodes to be modified are copied for the new heap.
However, the whole question was whether the compiler can elide this copying
for efficiency. If it mistakenly elides the copying of a node that is being
shared by some other part of the code, and makes the change in-place, that
will break the program (because that other part of the code will see the
change even though it shouldn't).
What I'm wondering is that it's probably way more common for the nodes
to not being shared (and thus have only one single owner), but how can
the compiler know that for sure in a complex program?
If such a data container is used only inside one single function and
its contents never passed anywhere else, the compiler may be able to
deduce that it can elide copying. However, in many (if not most) situations
such data containers will live for longer than one single function (after
all, that's the most common use of a data container) and used by several
different parts of the program. It's enough for two different parts of the
program to modify (or perhaps even just read) the same data container for
the in-place modifications becoming a program correctness hazard.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/6/2011 14:11, Warp wrote:
> What I'm wondering is that it's probably way more common for the nodes
> to not being shared (and thus have only one single owner), but how can
> the compiler know that for sure in a complex program?
Right. Consider the "insert" function itself. It calls nothing else that
mutates the heap except for "insert". So for the duration of the actual
insert call, it knows the heap isn't shared. Extend this concept a bit
(yes, that's fuzzy, I know) and with sufficient analysis, you can figure out
that when you do something like
x = insert 27 original
y = insert 56 x
z = insert 23 y
that y is an intermediate value that can't be shared with anything else.
(OK, maybe not in the heap case, but in a fair number of other such
structures, it's not uncommon it's possible to determine that. Again, I'm
not familiar with the details of how it's done.)
> and used by several different parts of the program.
If you compile those separately, yes, that can be problematic. If you
compile it all at the same time, or have more sophisticated linking (like a
VM, say), then the range over which the compiler can deduce a lack of
sharing is greater.
Remember, too, that various kinds of GC can tell you whether something is
shared or not. You could conceive of a copy-on-write sort of thing that only
does the copy if the reference count is >1.
> It's enough for two different parts of the
> program to modify (or perhaps even just read) the same data container for
> the in-place modifications becoming a program correctness hazard.
True. That's why it's better to leave it to the compiler than the
programmer. ;-)
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Is this supposed to be efficient?
>
> If your functional language is pure enough, your compiler can often
> optimize out the apparent inefficiency. Of course, that requires a
> Sufficiently Smart Compiler.
>
> In practice, it's less efficient, but not as obviously awful as it would
> appear.
In a way, it's a bit like SQL. In SQL, if you want to find the customer
name for each order, you say "take the Cartesian product of the order
table and a customer table, then go through the result and throw away
all rows except the ones where ord_cust = custID". If both tables are of
size N, then the first step is O(N^2) in time and space, and the second
step is O(N^2) in time and O(N) in space.
That's nauseatingly inefficient! But fortunately, every half-sane RDBMS
on the planet looks at that query and goes "ah-HAH! You're doing a table
join!" and replaces it with a vastly more efficient algorithm. (Be it a
hash-join or an index lookup or whatever.)
If SQL wasn't being run by a "sufficiently smart interpreter", it would
be too laughably inefficient to even consider using. The *only* reason
its so ubiquitous is that everybody has built really, *really* smart
interpreters. And everybody /relies on/ the query you actually write
being optimised into something very fast. Usually it works every well
indeed.
Of course, SQL isn't a general-purpose programming language. It solves
one problem well. (Although it's not quite the relational algebra...)
Haskell is a general-purpose programming language. You write constructs
which /look/ horrifyingly inefficient. And then the compiler does its
thing, and the end result is more efficient than you'd imagine. Sure,
probably not as fast as C, but fast enough.
Also: I love how this started out as "how easy is it to understand
Haskell?" and has once again degenerated into "Haskell must be really
slow". Which wasn't the question at all.
You know those C hackers? The ones who write horribly unmaintainable
code in the name of being a few clock cycles faster? The ones who are so
obsessed with using the minimum amount of CPU time and RAM that they
write horrid spaghetti code?
Yeah, everybody hates those guys. You know what their problem is? They
fail to realise that programs are judged on criteria *other* than
run-time efficiency. Obviously nobody /wants/ slow code. But then nobody
/wants/ buggy code, unmaintainable code, code that crashes, code that's
impossible to understand, code that takes months to write and debug.
There's a /reason/ people code stuff in C and not assembly. Even though
(in theory if not in practise) assembly is faster, people use C. As I
recall, there was a long time where people wouldn't use C++ because they
said it was "too slow", and that only C was "fast enough". (Which as
amusing, given that the Language Shootout claims that C++ is actually
marginally /faster/ than C...)
Haskell usually isn't as fast as C or C++. It's also a lot simpler to
program. Especially if you want parallelism. You ask me "how do I update
a heap without copying?" I ask you "how do you update a heap in a
thread-safe manner?" Immutable by default => thread-safe by default.
That's just one example of the kind of benefits that Haskell brings.
According to the Language Shootout, Haskell averages about 3x slower
than C. Java averages only 1.5 slower (but uses more memory than
Haskell). Then again, people actually write applications in Ruby, Python
and so forth. People build high-traffic websites with PHP and Perl. All
of these come in at *hundreds of times* slower than C. And it hasn't
dented their popularity at all.
Sometimes run-time efficiency isn't the most important thing.
(One could argue that although Perl is Turing-complete, it probably
shouldn't be regarded as a general-purpose language. It's probably
blisteringly fast for the tiny fraction of the language that most people
actually use. One could also argue that the Language Shootout is a
benchmark to see which language has the most zealous fans with the most
spare time...)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
