 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Haskell has a reputation [among people who've actually *heard* of it]
for being a bizarre, baffling and opaque language. Most people agree
that no sane human could possibly comprehend something so utterly weird
and confusing.
Which is strange, because to those of us that know it, Haskell is an
especially /simple/ language, which very directly allows you to express
what you want to say. Theories about its perceived "hardness" include
the unusual syntax, the unfamiliar mode of operation, the lack of good
documentation, the excessive amount of opaque mathematical jargon, or
possibly the ludicrous number of monad tutorials. I know Warp's
favourite theory is that people just don't "think functionally". But now
I've come up with my own suggestion:
Hypothesis: The Haskell language isn't hard. Typical Haskell *programs*
are hard.
Now what the heck do I mean by that? Well, to put it bluntly, Haskell is
an extraordinarily powerful language, so people tend to use it to solve
"hard" problems. It's not that there's anything hard about the Haskell
language itself. It's just that people only use Haskell to solve
problems that are hard to understand, using solutions that are even
harder to understand. After all, the /really cool thing/ about Haskell
is that you *can* solve hard problems with it.
To illustrate what I mean, consider a typical introductory Java
textbook. Such a thing will contain chapters about how to set up some
kind of Java compiler, the basic syntax rules of Java, how to create
variables, how to write loops, and so forth. It will probably have a
huge class reference at the back, because Java's standard class library
is frankly rococo. Throughout the text, you'll find little (and not so
little) code snippets which demonstrate one particular feature or idea.
But what actual /example programs/ might you find?
Obviously this varies by author, but typical programs will usually include:
- Hello world. (As required by RFC 2100.)
- What is your name?
- Guess which random number I just picked.
- My command-line arguments are...
- This is how you read and write files.
- Open a window containing every widget type and print a message every
time the user clicks something.
- A 4-function calculator. (Either CLI or GUI.)
- Tic Tac Toe.
- A simple client/server (so you can demonstrate network sockets).
- A simple program that runs in two threads.
- A simple program that runs in two threads and avoids race conditions.
- This is how you run SQL statements via ODBC.
- This is how you play media. (Sounds, pictures, video, etc.)
- One program that doesn't actually "do" anything, but implements an
insanely complex class hierarchy just so the authors can demonstrate
ever OO feature of Java ALL AT ONCE!
- Possibly a bad knock-off of MS Paint.
In other words, the example programs cover specific tasks line running
SQL or loading graphics or making network connections, and then a few
very simple things like Tic Tac Toe that take these elements and make a
minimally "useful" program out of them. Hey, it /is/ an introductory
book, right?
What might a typical introductory Haskell textbook contain? Well, there
aren't actually many of those in print. There's a surprising number of
books that assume that you /already know/ Haskell and use it as the
vehicle for implementing stuff. But there aren't many books that aim to
/teach/ you Haskell.
If you manage to find one, though, typical introductory programs might
include:
- The factorial function, the Fibonacci numbers, Pascal's triangle, the
prime numbers...
- A skeleton implementation of a self-balancing binary search tree.
- A small parser combinator library.
- A simple shell-style interpreter for the SKI combinator calculus.
- A domain-specific language for specifying search predicates.
- Hello World (in an advanced chapter, after you've finished learning
the monadic identities).
- A simple web server (so we can show how easy concurrency is).
- An implementation of the Barnes-Hut N-body simulation algorithm (so we
can show off Haskell's trippy parallelism support).
- A solution to the Santa Claus problem (showcasing Haskell's software
transactional memory).
Now take a step back for a moment and just look at that list. These
items are all very, *very* CS-heavy. I defy you to find me an
introductory Java textbook that teaches you how to build a
self-balancing binary search tree. Most Java programmers would retort
"the library already *has* a perfectly good BST implementation; why
write another?" Of course, writing a real, usable library isn't the
point; /enlightenment/ is the point. The difference, it appears, is that
Java programmers think that implementing a BST is pointless and silly,
while Haskell programmers think this is "instructive" and "interesting".
In short, the languages make different assumptions. Java seems to think
that you're either building enterprisey DB front-ends (either desktop
applications, browser applets or server-side HTML generators) or
scripting DVD menu pages. Haskell, on the other hand, seems to fully
expect you to be designing a compiler or something.
In case you think my example page above is exaggerated, let's see what
example code is contained in Real World Haskell, an actual book actually
published by O'Reilly, an actual publisher. The book contains:
- A Haskell to JSON conversion library. (Includes a small
text-formatting library as a component.)
- A function to translate glob patterns into (POSIX) regular expressions.
- A domain-specific language for expressing file search predicates,
together with an engine that searches the file system for matches.
- Build a trivial parser monad and use it to parse the PGM file format.
(I.e., write a program that loads PGM images.)
- A program that loads a PPM image of a barcode, and decodes the digits
of the barcode. (EAN-13 barcodes only.)
- A program to parse /etc/passwd and allow interactive username lookups.
- Half a dozen small Parsec examples, parsing CSV files, JSON, HTTP
headers, etc.
- A library implementing a bloom filter.
How many Java textbooks teach you how to read barcodes?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 02/09/2011 04:36 PM, Invisible wrote:
> Hypothesis: The Haskell language isn't hard. Typical Haskell *programs*
> are hard.
Let's test that hypothesis. Consider the following example:
module Main where
import System.IO
import System.Random
main = do
x <- randomRIO (1, 100)
main_loop x
main_loop x = do
putStr "Guess: "
hFlush stdout
l <- getLine
let g = read l
if g == x
then putStrLn "Correct."
else do
if g < x
then putStrLn "Too low."
else putStrLn "Too high."
main_loop x
This is written in Haskell. However, I would expect that anybody
familiar with computer programming should be able to figure out what
this does, without knowing anything at all about Haskell. I mean, you
couldn't /write/ this code, but you can /read/ it and figure out what it
does. Which would seem to strongly contradict "Haskell is incomprehensible".
...or maybe I'm just delusional from having spent too long with Haskell?
Maybe it only looks readable to my eyes. What do we say, people?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] dev null> wrote:
> Let's test that hypothesis. Consider the following example:
> module Main where
> import System.IO
> import System.Random
> main = do
> x <- randomRIO (1, 100)
> main_loop x
> main_loop x = do
> putStr "Guess: "
> hFlush stdout
> l <- getLine
> let g = read l
> if g == x
> then putStrLn "Correct."
> else do
> if g < x
> then putStrLn "Too low."
> else putStrLn "Too high."
> main_loop x
That doesn't look functional at all. It looks imperative.
Throw in some functional tricks (such as infinite lists, currying and
such) and it becomes harder to figure out.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le 2011/09/05 04:52, Invisible a écrit :
> On 02/09/2011 04:36 PM, Invisible wrote:
>
>> Hypothesis: The Haskell language isn't hard. Typical Haskell *programs*
>> are hard.
>
> Let's test that hypothesis. Consider the following example:
>
> module Main where
>
> import System.IO
> import System.Random
>
> main = do
> x <- randomRIO (1, 100)
> main_loop x
>
> main_loop x = do
> putStr "Guess: "
> hFlush stdout
> l <- getLine
> let g = read l
> if g == x
> then putStrLn "Correct."
> else do
> if g < x
> then putStrLn "Too low."
> else putStrLn "Too high."
> main_loop x
>
> This is written in Haskell. However, I would expect that anybody
> familiar with computer programming should be able to figure out what
> this does, without knowing anything at all about Haskell. I mean, you
> couldn't /write/ this code, but you can /read/ it and figure out what it
> does. Which would seem to strongly contradict "Haskell is
> incomprehensible".
>
> ...or maybe I'm just delusional from having spent too long with Haskell?
> Maybe it only looks readable to my eyes. What do we say, people?
I think it's the first time I see actual Haskell code, and I can read
that one easily.
But,then, it's a prety trivial example.
Alain
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 05/09/2011 09:52 AM, Invisible wrote:
> ...or maybe I'm just delusional from having spent too long with Haskell?
Trivial program... is trivial.
It seems everybody agrees on that. Now let's try the sort of code that
typically appears in an introductory Haskell textbook:
module Heap
(
MinHeap (), empty, is_empty,
top, insert, delete_top,
union, size, to_list, from_list, heap_sort
)
where
data MinHeap x = Leaf | Node x (MinHeap x) (MinHeap x)
empty :: MinHeap x
empty = Leaf
is_empty :: MinHeap x -> Bool
is_empty Leaf = True
is_empty _ = False
top :: MinHeap x -> x
top (Leaf ) = error "empty heap"
top (Node x _ _) = x
insert :: Ord x => x -> MinHeap x -> MinHeap x
insert x' (Leaf ) = Node x' Leaf Leaf
insert x' (Node x h0 h1) = Node (min x x') (insert (max x x') h1) h0
delete_top :: Ord x => MinHeap x -> MinHeap x
delete_top (Leaf ) = error "empty heap"
delete_top (Node _ h0 h1) = union h0 h1
union :: Ord x => MinHeap x -> MinHeap x -> MinHeap x
union h0 h1 =
case (h0, h1) of
(Leaf, _ ) -> h1
(_ , Leaf) -> h0
(_ , _ ) ->
if top h0 < top h1
then Node (top h0) h1 (delete_top h0)
else Node (top h1) h0 (delete_top h1)
size :: MinHeap x -> Int
size (Leaf ) = 0
size (Node _ h0 h1) = 1 + size h0 + size h1
to_list :: Ord x => MinHeap x -> [x]
to_list (Leaf ) = []
to_list (Node x h0 h1) = x : to_list (union h0 h1)
from_list :: Ord x => [x] -> MinHeap x
from_list = foldr insert empty
heap_sort :: Ord x => [x] -> [x]
heap_sort = to_list . from_list
(This one - or something resembling it - appears in "The Fun of
Programming", Jeremy Gibbons & Oege de Moor, Palgrave Macmillan, in
chapter 1. Then again, strictly this isn't a book about learning
Haskell. It's about functional programming in general - as best as I can
tell...)
This is classic functional programming. The only thing missing is that
there's no high-order functions or type-level programming. It's got just
about everything else. Now let's see if Warp's claims hold up.
While the identifier names are strongly suggestive, I doubt anybody not
mildly fuent in Haskell is going to figure out what's actually going on
here. I'll post a Java translation in a minute. Then we can see whether
the program becomes clearer (i.e., Haskell is the problem) or remains
opaque (i.e., the algorithm is the problem).
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 05/09/2011 07:17 PM, Orchid XP v8 wrote:
> While the identifier names are strongly suggestive, I doubt anybody not
> mildly fuent in Haskell is going to figure out what's actually going on
> here. I'll post a Java translation in a minute. Then we can see whether
> the program becomes clearer (i.e., Haskell is the problem) or remains
> opaque (i.e., the algorithm is the problem).
OK, so attempting to compare like for like, here's the most "natural"
way I could think of to implement this in Java:
public abstract class MinHeap
{
public abstract bool is_empty();
public abstract int top();
public abstract MinHeap insert(int x);
public abstract MinHeap delete_top();
public abstract MinHeap union(MinHeap h);
public abstract int size();
}
public class MinHeap_Emtpy extends MinHeap
{
private MinHeap_Empty() {}
public static MinHeap_Empty empty = new MinHeap_Empty();
public bool is_empty() {return true;}
public int top() // Throw exception
public MinHeap insert(int x)
{return new MinHeap_Node(x, null, null);}
public MinHeap delete_top() // Throw exception
public MinHeap union(MinHeap h) {return h;}
public int size() {return 0;}
}
public class MinHeap_Node extends MinHeap
{
public int datum;
public MinHeap child0, child1;
public bool is_empty() {return false;}
public int top() {return this.datum;}
public MinHeap insert(int x)
{
let h = this.datum;
let l = x;
if (h < l) {h = x; l = this.datum;}
return new MinHeap_Node(l, this.child1.insert(h), this.child0);
}
public MinHeap delete_top() {return this.child0.union(this.child1);}
public MinHeap union(MinHeap h)
{
if (h.is_empty()) return this;
MinHeap_Node that = (MinHeap_Node)h;
if (this.datum < that.datum)
return new MinHeap_Node(this.datum, that, this.delete_top());
return new MinHeap_Node(that.datum, this, that.delete_top());
}
public int size()
{return 1 + this.child0.size() + this.child1.size();}
}
Differences:
- I don't know how Java does generics, so this min-heap handles int only.
- I left out the list conversion stuff, because I'm not sure about
Java's container types off the top of my head. The "idiomatic" way is
probably to define an interator or something anyway...
- It's a while since I did Java. This might not actually compile for one
reason or other. (In particular, I'm fuzzy on how auto-constructors work...)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> insert :: Ord x => x -> MinHeap x -> MinHeap x
> insert x' (Leaf ) = Node x' Leaf Leaf
> insert x' (Node x h0 h1) = Node (min x x') (insert (max x x') h1) h0
This is a good example of where it becomes confusing. Even after
studying it for a few minutes I can't really figure out what is it
that it's doing. (Or, more precisely *how* it's doing it. The 'insert'
name makes it obvious what is it that it does, but the code doesn't make
it at all clear how.)
Maybe the problem is that in an imperative language the different
situations would be more explicitly expressed with an 'if...then...else'
block. Here it's not clear at all what is it that the code is expressing.
Of course it doesn't help that the syntax is quite uncommon, and the
meaning of the different operators isn't clear. (For instance, it's unclear
whether the ' is some kind of operator, and if it is, what exactly its role
is. If it isn't an operator but somehow just part of the variable name, it's
highly unusual.)
The lack of separators is also confusing to someone who is accustomed to
programming languages that use separators.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 05/09/2011 07:45 PM, Warp wrote:
> Orchid XP v8<voi### [at] devnull> wrote:
>> insert :: Ord x => x -> MinHeap x -> MinHeap x
>> insert x' (Leaf ) = Node x' Leaf Leaf
>> insert x' (Node x h0 h1) = Node (min x x') (insert (max x x') h1) h0
>
> This is a good example of where it becomes confusing. Even after
> studying it for a few minutes I can't really figure out what is it
> that it's doing.
Hmm, OK. Apparently I've spent longer doing this than I thought...
Is the Java translation any easier to grok? Or is that equally baffling?
> (Or, more precisely *how* it's doing it. The 'insert'
> name makes it obvious what is it that it does, but the code doesn't make
> it at all clear how.)
Well, yeah, you can take a stab at identifier names in most languages.
> Maybe the problem is that in an imperative language the different
> situations would be more explicitly expressed with an 'if...then...else'
> block. Here it's not clear at all what is it that the code is expressing.
I can rephrase it to
insert x' h =
case h of
Leaf -> Node x' Leaf Leaf
Node x h0 h1 -> Node (min x x') (insert (max x x') h1) h0
if you prefer. I don't suppose that's any more enlightening though.
The irony is that "case" is a more powerful version of "if/then/else".
(The latter is rigorously a special-case of the former.) Haskell's
"case" is like what other languages have, on steriods. On the other
hand, if/then/else is pretty self-explanatory, whereas a case-expression
isn't quite so immediately obvious.
The fact that you can write [what appear to be] multiple definitions of
the same function as a short-cut to a case-expression isn't the most
intuitive thing. Until somebody tells you that's what it means.
> Of course it doesn't help that the syntax is quite uncommon, and the
> meaning of the different operators isn't clear.
Sure. You can find strange operators in any language; I guess one of the
biggest things about Haskell is that its syntax just plain /isn't like/
anything else.
C, C++, C#, Java, JavaScript, Pascal and a half-dozen other languages
all have virtually identical function-call syntax, and (apart from
Pascal) the rest of the basic guts of the language has mild syntactic
differences. So if you know any of those languages, you can take a stab
at reading any of the others. Haskell is utterly different. Doesn't even
resemble anything else. (Except other obscure languages like ML.)
> (For instance, it's unclear
> whether the ' is some kind of operator, and if it is, what exactly its role
> is. If it isn't an operator but somehow just part of the variable name, it's
> highly unusual.)
It's not an operator, merely part of the variable name. It's a de facto
Haskell idiom; if you have a variable named foo, the new version of it
is named foo'. (If you have more than two versions, it's probably better
to number them, although you do see people write foo'' and even foo'''.)
Apparently it's supposed to look like the mathematical "prime" symbol
(which is more usually used for derivatives, actually).
I'll grant you that one's /highly/ non-obvious. I could perhaps have
called it y instead of x' for increased clarity. That's only one of your
points, though.
> The lack of separators is also confusing to someone who is accustomed to
> programming languages that use separators.
Sure. You do see a lot of people look at an expression like
foo x y + z bar
and think to themselves "now what the hell does that mean?" Knowing the
barest bit of Haskell, possible options include:
- foo(x, y + z, bar)
- foo(x, y) + z(bar)
- foo(x, y, +, z, bar)
It's also common for beginner's Haskell code to contain more brackets
than a typical Lisp snippet because it's so disconcerting to figure out.
You apparently can't see far enough into the syntax to realise this, but
I think perhaps part of the problem is the whole symmetry of it all.
The syntax for /inspecting/ data is identical to the syntax for
/constructing/ data. Which makes the language very regular and
beautiful, but it also perhaps makes it rather baffling to anybody
trying to figure out whether you're inspecting or constructing stuff.
The syntax for a tuple /type/ is identical to the syntax for a tuple
/value/. Compare:
('1', 2, 3.4, "five") :: (Char, Int, Double, String)
Thing on the left is data. Thing on the right is a type signature. Now
consider
(x, y, z) :: (x, y, z)
This perfectly valid Haskell expression has three value variables on the
left, and (unrelated but identically named) three type variables on the
right.
The exact same thing happens with list values and list types.
Here, the very symmetry of the language is arguably somewhat baffling.
Patterns look like expressions. Types look like values. Once you know
Haskell modestly well, you realise that patterns /only/ go in certain
places, and everything else is an expression. Types /only/ go in certain
places, so everything else is values. But until you reach that point,
the language design certainly isn't helping you much.
PS. I just discovered that you can create local operator names in the
same way that you create local variables. So you can make a function
where the same operator name changes its meaning on each recursive call
to the function. How evil is that?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/5/2011 11:45, Warp wrote:
> Orchid XP v8<voi### [at] devnull> wrote:
>> insert :: Ord x => x -> MinHeap x -> MinHeap x
>> insert x' (Leaf ) = Node x' Leaf Leaf
>> insert x' (Node x h0 h1) = Node (min x x') (insert (max x x') h1) h0
>
> This is a good example of where it becomes confusing. Even after
> studying it for a few minutes I can't really figure out what is it
> that it's doing. (Or, more precisely *how* it's doing it. The 'insert'
> name makes it obvious what is it that it does, but the code doesn't make
> it at all clear how.)
I think part of it may be that you're thinking "insert" actually inserts
something in the heap. Nope! "insert" is a function that when given a value
and a heap, gives you back the new heap you would have were you to insert
that given value into that given heap.
--
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/5/2011 11:45, Warp wrote:
> > Orchid XP v8<voi### [at] devnull> wrote:
> >> insert :: Ord x => x -> MinHeap x -> MinHeap x
> >> insert x' (Leaf ) = Node x' Leaf Leaf
> >> insert x' (Node x h0 h1) = Node (min x x') (insert (max x x') h1) h0
> >
> > This is a good example of where it becomes confusing. Even after
> > studying it for a few minutes I can't really figure out what is it
> > that it's doing. (Or, more precisely *how* it's doing it. The 'insert'
> > name makes it obvious what is it that it does, but the code doesn't make
> > it at all clear how.)
> I think part of it may be that you're thinking "insert" actually inserts
> something in the heap. Nope! "insert" is a function that when given a value
> and a heap, gives you back the new heap you would have were you to insert
> that given value into that given heap.
What happens to the old heap?
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/5/2011 14:36, Warp wrote:
> What happens to the old heap?
It's functional. The old heap is still in x, where you passed it in. Or x'.
Or something like that.
You would have to say
newheap := insert 27 oldheap
or some such. Then the old heap is in oldheap and the new heap is in newheap.
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le 2011/09/05 15:28, Orchid XP v8 a écrit :
>
> PS. I just discovered that you can create local operator names in the
> same way that you create local variables. So you can make a function
> where the same operator name changes its meaning on each recursive call
> to the function. How evil is that?
>
That's an uterly devilish and abominaly sadistic way to obfuscate your code.
It's totaly /beyong/ *EVIL*.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 06/09/2011 02:29 AM, Alain wrote:
> Le 2011/09/05 15:28, Orchid XP v8 a écrit :
>
>>
>> PS. I just discovered that you can create local operator names in the
>> same way that you create local variables. So you can make a function
>> where the same operator name changes its meaning on each recursive call
>> to the function. How evil is that?
>>
>
> That's an uterly devilish and abominaly sadistic way to obfuscate your
> code.
> It's totaly /beyong/ *EVIL*.
Heh. If Haskell had obfuscated coding contests...
...my god, it's too terrifying to imagine! o_O
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 05/09/2011 11:19 PM, Darren New wrote:
> On 9/5/2011 14:36, Warp wrote:
>> What happens to the old heap?
>
> It's functional. The old heap is still in x, where you passed it in. Or
> x'. Or something like that.
Actually, x' is the new element you're inserting, not the heap. I didn't
give the heap itself a variable name at all.
> You would have to say
> newheap := insert 27 oldheap
> or some such. Then the old heap is in oldheap and the new heap is in
> newheap.
Quite.
(Although the actual syntax calls for "=", not ":=", but whatever.)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> This is a good example of where it becomes confusing.
>
>> I think part of it may be that you're thinking "insert" actually inserts
>> something in the heap. Nope! "insert" is a function that when given a value
>> and a heap, gives you back the new heap you would have were you to insert
>> that given value into that given heap.
I'm not sure a person unfamiliar with Haskell would even get that far.
> What happens to the old heap?
Nothing. (That's exactly the point, of course.)
If nobody is using the old heap any more, the garbage collector will
remove it at some point.
If you /really/ wanted to split hairs, the insert function is only
duplicating log N heap nodes. The remaining N - log N nodes (and the
data they point to) are shared between the old and new heaps. And if the
old heap is no longer needed, the log N nodes it doesn't share with the
new heap will automatically be removed eventually.
And if you really, really want to get picky, actually saying
heap' = insert 27 heap
merely creates an expression node which heap' points to. Only if you
attempt to /inspect/ this heap is any code executed. (And even then,
inspecting each node only causes that single node to be constructed.
It's child nodes remain unevaluated until you look at them.)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 05/09/2011 07:45 PM, Warp wrote:
> Orchid XP v8<voi### [at] devnull> wrote:
>> insert :: Ord x => x -> MinHeap x -> MinHeap x
>> insert x' (Leaf ) = Node x' Leaf Leaf
>> insert x' (Node x h0 h1) = Node (min x x') (insert (max x x') h1) h0
>
> This is a good example of where it becomes confusing. Even after
> studying it for a few minutes I can't really figure out what is it
> that it's doing.
The first line is a type signature. It says
"For any type x which has ordering operations, this function takes an
x and a MinHeap x and returns a MinHeap x."
The next two lines define the function. Each line conceptually means "if
the function call looks like the thing on the left, the result looks
like the thing on the right".
Therefore, if I were to write
insert 5 Leaf
it should be just as if I had written
Node 5 Leaf Leaf
The general rule of Haskell is that any name that begins with a *lower
case* letter is a variable name. (This isn't merely a convention, it is
formally part of the actual language syntax.) This is why "x" is a
variable name, but "Leaf" is not.
(If you're paying attention, you'll notice that "insert" is a variable
name by these rules. In Haskell, a named function is simply a named
variable who's value just happens to be a function. Which is kinda
weird, but consistent.)
So, textually, insert 5 Leaf means Node 5 Leaf Leaf. Operationally, what
does that actually /mean/? Well, in more typical syntax it would be
something like
MinHeap insert(x)
{
MinHeap out = new MinHeap_Node();
out.datum = x';
out.child0 = Leaf.singleton;
out.child1 = Leaf.singleton;
return out;
}
(Since "Leaf" has no data fields, it is essentially a global constant.)
In other words, we're constructing a new Node object and setting it to
point to the new datum we're inserting, and setting both of its children
to be the empty heap.
So how about that last line?
insert x' (Node x h0 h1) = ...
So if you're inserting into a heap that /isn't/ empty, then
x' is the thing you want to insert.
x is the datum in the root node of the heap.
h0 is the left child of the root node.
h1 is the right child of the root node.
Given that, the right-hand side says
... = Node (min x x') (insert (max x x') h1) h0
That parses basically as
... = new Node(min(x, x'), insert(max(x, x'), h1), h0);
In other words, create a new heap node, where the datum is x or x',
whichever is lowest. The left child is the result of running
insert(max(x, x'), h1) - in other words, recursively insert x or x'
(whichever is highest) into h1. The right child is h0.
So, we compare the existing root datum to the new datum, and keep the
lowest one in the new root node. We then recursively insert the other
datum into one of the child heaps.
Notice carefully how h0 and h1 get swapped around. This keeps the heap
balanced. (If you stare at delete_top, you'll see it also swaps the
children around - and deletes from the other side.) I haven't formally
proven it, but I /think/ this arrangement keeps the tree balanced for
all valid operation sequences. Certainly it does if you repeatedly
insert items; I'm not 100% sure about interleaved inserts and deletes.
So really, there's two ways to interpret Haskell functions. You can view
each one as a textual substitution. Given pencil and paper, you can
expand out the work that each one does. For example:
insert 1 (insert 2 (insert 3 (insert 4 empty)))
insert 1 (insert 2 (insert 3 (insert 4 Leaf))) [Because empty = Leaf]
insert 1 (insert 2 (insert 3 (Node 4 Leaf Leaf)))
insert 1 (insert 2 (Node 3 (insert 4 Leaf) Leaf))
insert 1 (insert 2 (Node 3 (Node 4 Leaf Leaf) Leaf))
insert 1 (Node 2 (insert 3 Leaf) (Node 4 Leaf Leaf))
insert 1 (Node 2 (Node 3 Leaf Leaf) (Node 4 Leaf Leaf))
Node 1 (insert 2 (Node 4 Leaf Leaf)) (Node 3 Leaf Leaf)
Node 1 (Node 2 (insert 4 Leaf) Leaf) (Node 3 Leaf Leaf)
Node 1 (Node 2 (Node 4 Leaf Leaf) Leaf) (Node 3 Leaf Leaf)
It's not hard to throw together a little program that shunts text around
like this. (Although the brackets are fiddly if you want to do it right.)
If you draw a little graph, the final expression there looks like
Node 1
Node 2 Node 3
Node 4 Leaf Leaf Leaf
Leaf Leaf
Which is a balanced tree. (As balanced as a tree containing 4 items can
be, anyway.)
So textually, that's how to run Haskell. Operationally, the thing on the
left checks which "constructor" is present (i.e., whether a node is a
Leaf or a Node), and then binds variables to things. It then constructs
the value described on the right.
It's not shown in my example, but the notation is quite powerful. It
lets you do things like inspect multiple levels of the tree:
rotate :: MinHeap x -> MinHeap x
rotate (Node x1 (Node x2 c1 c2) c3) = Node x2 c1 (Node x1 c2 c3)
That's a tree rotation [which obviously isn't a valid thing to do to a
min-heap tree, but you get the idea]. Every time "Node" appears on the
left, it means "this part has to be a Node object". Every time it
appears on the right, it means "please construct a new Node object".
Once you get over the notation, it's actually a very clear and succinct
way to work. Consider the alternative:
function rotate(root)
{
if (root.type == "node")
{
x1 = root.datum;
c3 = root.child1;
child = root.child0;
if (child.type == "node")
{
x2 = child.datum;
c1 = child.child0;
c2 = child.child1;
return new Node(x2, c1, new Node(x1, c2, c3));
}
}
}
All that code to do the same thing as the 1-liner above. Not only is the
Haskell version shorter, it's clearer: It says "my input must look like
THIS, and then I will change it to look like THAT". You don't have to
mentally execute a series of one-at-a-time baby steps to see what's
happening. It's a bit like
temp1 = 1 + 2;
temp2 = 3 + 4;
temp3 = temp1 * temp2;
temp4 = temp3 ^ 2;
verses
temp4 = ((1+2) * (3+4))^2;
The latter is not only shorter, but infinitely clearer.
...again, "more maybe I'm just delusional"...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 05/09/2011 07:45 PM, Warp wrote:
> The lack of separators is also confusing to someone who is accustomed to
> programming languages that use separators.
Don't try Lisp. ;-) (Or Smalltalk. Or Tcl. Or...)
Anyway, just for giggles, I wanted to see if I could hack the language
hard enough to make it support separators. The answer is... yeah, kinda.
insert|< 5 # my_heap >|j
I can't get it to use a comma, colon, semicolon or any similarly
separator-like symbol, since these are all reserved symbols. The best I
could manage is #, @, $ or similar. (I did try more unusual Unicode
symbols, but that crashed the compiler - ridiculously enough...)
Obviously, the way I did this was to define some new operators. I could
have gone for
insert< 5 # my_heap >j
except that "<" and ">" are already in use. (You can reuse them... but
would you want to?)
You may also notice the stray "j" at the end. That's not a semicolon,
it's the letter J. Haskell doesn't support unary operators, only binary.
So the final >| must have two operands. It actually ignores the second one.
The code is quite simple:
f |< x = f x
f # x = f x
x >| y = x
j = undefined
That's literally it.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 06/09/2011 11:23 AM, Invisible wrote:
> Anyway, just for giggles, I wanted to see if I could hack the language
> hard enough to make it support separators. The answer is... yeah, kinda.
>
> insert|< 5 # my_heap >|j
I managed to go one better:
insert&(5, my_heap)
Works for any valid Haskell function. With one small catch:
foo&() -- Works fine.
foo&(1) -- Doesn't work at all.
foo&(1, 2) -- Works fine.
foo&(1, 2, 3) -- Works fine.
...
Basically, the syntax "(1, 2, 3)" defines what Haskell calls a "tuple".
You can write functions that accept a tuple:
add (x, y, z) = x + y + z
You then then write "add (1, 2, 3)", but due to Haskell's parsing rules,
"add(1, 2, 3)" (without the space) is also valid. And looks exactly like
a function call in any other language.
Trouble is, it works only if the function you call is /expecting/ a
tuple. As far as Haskell is concerned, "add" is a 1-argument function,
not a 3-argument function.
With some clever type hackery, you can make a "&" operator (or any other
operator name you'd like, providing it isn't reserved) that "un-tuples"
a tuple. Using this, you can supply tuples to any existing Haskell function.
There's a glitch, however: Haskell is tuple sizes from 2 upwards. (IIRC,
the language spec guarantees that sizes up to 5 will exist.) Haskell
also has a size-zero tuple, commonly used as a dummy value for when you
don't actually need to put data somewhere. But it doesn't have a size-1
tuple. Because, let's face it, what would be the point of that?
As a result of this, foo&(5) is actually foo&5. And I can't get it so
that that works. I can make it so a different sort of bracket works, or
a different operator works, but I can't make it consistent with the rest.
And so ends today's lesson in raping your language syntax. :-)
{-# LANGUAGE TypeFamilies, MultiParamTypeClasses, FlexibleInstances #-}
module Test where
class Tuple t r where
type Function t r :: *
(&) :: Function t r -> t -> r
instance Tuple () r where
type Function () r = r
f & () = f
instance Tuple (x,y) r where
type Function (x,y) r = x -> y -> r
f & (x,y) = f x y
instance Tuple (x,y,z) r where
type Function (x,y,z) r = x -> y -> z -> r
f & (x,y,z) = f x y z
instance Tuple (x,y,z,w) r where
type Function (x,y,z,w) r = x -> y -> z -> w -> r
f & (x,y,z,w) = f x y z w
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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?
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> On 05/09/2011 07:45 PM, Warp wrote:
> > The lack of separators is also confusing to someone who is accustomed to
> > programming languages that use separators.
> Don't try Lisp. ;-)
I thought Lisp separates everything with parentheses.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 06/09/2011 04:05 PM, Warp wrote:
> Invisible<voi### [at] devnull> wrote:
>> On 05/09/2011 07:45 PM, Warp wrote:
>
>>> The lack of separators is also confusing to someone who is accustomed to
>>> programming languages that use separators.
>
>> Don't try Lisp. ;-)
>
> I thought Lisp separates everything with parentheses.
In Haskell, you say
abc def ghi
In Lisp, you say
(abc def ghi)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 06/09/2011 04:03 PM, 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?
Modifying log N nodes of the old heap to construct the new one? I'd say
it's reasonably efficient, yes.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> On 06/09/2011 04:03 PM, 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?
> 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. (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.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> On 06/09/2011 04:05 PM, Warp wrote:
> > Invisible<voi### [at] devnull> wrote:
> >> On 05/09/2011 07:45 PM, Warp wrote:
> >
> >>> The lack of separators is also confusing to someone who is accustomed to
> >>> programming languages that use separators.
> >
> >> Don't try Lisp. ;-)
> >
> > I thought Lisp separates everything with parentheses.
> In Haskell, you say
> abc def ghi
Are those three commands or one command with two arguments?
> In Lisp, you say
> (abc def ghi)
Because, AFAIK, that is the latter.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> 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] 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.
--
- 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 06/09/2011 09:28 PM, Warp wrote:
> 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.
I used to think that the compiler magically performed these kinds of
optimisation somehow. I've gradually learned that this isn't the case.
Oh, sure, if you write one function that puts some data into a box, and
another function that immediately takes the data out of that box again,
the box will probably be optimised away. But for something like updating
a list / tree / whatever, it's usually not feasible to optimise out the
copying.
(There /are/ frameworks designed to spot long chains of container
manipulations and inline them into a giant nested loop. But that's not
compiler magic, that's clever user-level programming. The example I
posted contains no such magic.)
> (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.)
Let us be clear about exactly what is copied:
If you have a heap which contains N internal nodes (since there is only
"one" leaf node, shared by all heaps in the program) and you insert a
new item into that heap, then O(log N) new heap nodes get constructed.
Each [internal] heap node consists of 4 pointers. One points to
something resembling a vtable [that's how you can tell Node and Leaf
apart], one points to the datum, and the other two point to the child nodes.
So copying an internal node amounts to copying (and possibly altering) 4
pointers. This /regardless/ of the type of data the heap holds. Even if
it holds arbitrary-precision integers, you're still only copying 4
pointers. The integers haven't changed, and so are not copied.
It does seem a pity that in the [very common] case of starting from an
empty heap and repeatedly inserting new items into it, you have to keep
continually generating these new nodes and then throwing them away. In
mitigation, the GC is heavily optimised for this activity pattern.
Allocations are cheap. They happen in a per-core allocation area (so no
cache coherency issues), and each allocation is O(1). When the
allocation area fills up, a GC sweep happens. Because the allocation
area is quite small, it can be swept very quickly. The sweep identifies
garbage, frees it, and defragments the free space (so that allocation is
still O(1) in all cases).
It would be faster if you didn't have to do all this work, but it's not
as slow as you'd think.
There are two key scenarios where immutable data becomes a Big Win:
First, there's parallel programming. Immutable data is thread-safe data.
It /cannot/ change while you're examining it, so race conditions are a
non-issue. Obviously if you want to /communicate/ between threads,
that's another matter. But you don't ever have to worry about making one
thread wait to update something until after the other thread has
definitely finished using it. You won't ever see bugs where you mutate
something and then discover that another thread was actually still
reading it.
Second, backtracking search problems. You might think that copying stuff
every time you want to change it is inefficient, but if you're doing
some kind of search problem where you want to search multiple avenues,
then still having the old copy around drastically simplifies the
algorithm, and probably /increases/ efficiency. Because the alternative
is to deduce (or remember) what you did, and then manually undo it if
you need to backtrack.
Some guy at Google wrote a paper about translating a Python (?) system
to Haskell, and actually devoted a whole section to the problems of
trying to enforce immutability in Python, and the difficulties of doing
without it. Immutable data was sited as one of Haskell's biggest advantages.
The one place where immutability /does/ bit is arrays. Almost all
Haskell data structures are linked lists or trees of some kind, because
that way the copying is cheap. But if you update one index of a
one-million index array, you've got to copy a contiguous block of a
million elements. Not fast. Immutable arrays are great as super-fast
lookup tables, but unless the data changes very infrequently, you end up
needing mutable arrays. Immutable arrays just aren't all that useful.
[Insert rant about how Haskell's array implementation sucks...]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/7/2011 2:22, Invisible wrote:
> then O(log N) new heap nodes get constructed.
Which, incidentally, is the same number of nodes you'd have to update in a
mutable heap, too.
> But you don't ever have to worry about making one thread
> wait to update something until after the other thread has definitely
> finished using it.
That's not strictly true. It's entirely possible in modern processors that
the pointer gets written and is visible to other processors before the data
it points to gets flushed from the cache into main memory.
> Immutable arrays are great as super-fast lookup tables, but unless the data
> changes very infrequently, you end up needing mutable arrays. Immutable
> arrays just aren't all that useful.
Some of the google stuff is cool in that way. You can imagine you don't want
to update the entire file that holds the entire web every time you scan a
new document.
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 08/09/2011 05:09 AM, Darren New wrote:
> On 9/7/2011 2:22, Invisible wrote:
> > then O(log N) new heap nodes get constructed.
>
> Which, incidentally, is the same number of nodes you'd have to update in
> a mutable heap, too.
Indeed. The only difference is that with Haskell, you *copy* these nodes
rather than simply modify them in-place.
>> But you don't ever have to worry about making one thread
>> wait to update something until after the other thread has definitely
>> finished using it.
>
> That's not strictly true. It's entirely possible in modern processors
> that the pointer gets written and is visible to other processors before
> the data it points to gets flushed from the cache into main memory.
No, that's exactly what the "cache coherence" protocol prevents.
>> Immutable arrays are great as super-fast lookup tables, but unless the
>> data
>> changes very infrequently, you end up needing mutable arrays. Immutable
>> arrays just aren't all that useful.
>
> Some of the google stuff is cool in that way. You can imagine you don't
> want to update the entire file that holds the entire web every time you
> scan a new document.
If defies my comprehension that what Google does is actually physically
possible, but anyway...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/8/2011 1:14, Invisible wrote:
> No, that's exactly what the "cache coherence" protocol prevents.
Sure. I'm just saying that saying "it's write-once" doesn't automatically
mean it's thread safe in a modern multi-processor. The generated code
actually has to take some care to tell the processor to flush cache lines
and such.
> If defies my comprehension that what Google does is actually physically
> possible, but anyway...
It kind of boggles my mind too. Just the complexity of the monitoring stuff
is stunning, let alone actually getting work done. :-)
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 08/09/2011 06:24 PM, Darren New wrote:
> On 9/8/2011 1:14, Invisible wrote:
>> No, that's exactly what the "cache coherence" protocol prevents.
>
> Sure. I'm just saying that saying "it's write-once" doesn't
> automatically mean it's thread safe in a modern multi-processor. The
> generated code actually has to take some care to tell the processor to
> flush cache lines and such.
According to the documentation I read, this is automatic. As in, the
code doesn't have to take any explicit action at all to ensure that all
processors see a consistent image of main memory. It's just that if
several cores try to access the same area at once, it gets very, very slow.
>> If defies my comprehension that what Google does is actually physically
>> possible, but anyway...
>
> It kind of boggles my mind too. Just the complexity of the monitoring
> stuff is stunning, let alone actually getting work done. :-)
Apparently it's one of the monitoring and load-balancing systems they
translated to Haskell...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/8/2011 11:36, Orchid XP v8 wrote:
> According to the documentation I read, this is automatic.
It certainly depends on the CPU and architecture.
http://en.wikipedia.org/wiki/Memory_barrier
You also have to make sure you're not caching something in a register that
you've written out the pointer to.
>> It kind of boggles my mind too. Just the complexity of the monitoring
>> stuff is stunning, let alone actually getting work done. :-)
>
> Apparently it's one of the monitoring and load-balancing systems they
> translated to Haskell...
What is?
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 09/09/2011 05:14 PM, Darren New wrote:
> On 9/8/2011 11:36, Orchid XP v8 wrote:
>> According to the documentation I read, this is automatic.
>
> It certainly depends on the CPU and architecture.
Well, yes, I was referring to the only architecture in existence that
people are likely to be writing desktop applications for. :-P
> You also have to make sure you're not caching something in a register
> that you've written out the pointer to.
This is certainly true. That's why C has "volatile", for example.
>>> It kind of boggles my mind too. Just the complexity of the monitoring
>>> stuff is stunning, let alone actually getting work done. :-)
>>
>> Apparently it's one of the monitoring and load-balancing systems they
>> translated to Haskell...
>
> What is?
I saw a paper a while back about how Google (I forget which center)
translated part of the monitoring system from Python to Haskell, and
documented what they did and didn't find beneficial about this.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/9/2011 9:57, Orchid XP v8 wrote:
> Well, yes, I was referring to the only architecture in existence that people
> are likely to be writing desktop applications for. :-P
I think even amongst Intel and AMD x64 and x86 architectures, this varies.
I'm pretty sure it's not 100% automatic or there wouldn't be instructions
for causing it to happen.
> I saw a paper a while back about how Google (I forget which center)
> translated part of the monitoring system from Python to Haskell, and
> documented what they did and didn't find beneficial about this.
Ah. Well, there's monitoring out the wazoo here, so I'm quite certain they
didn't rewrite even a majority of it.
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 09/09/2011 07:09 PM, Darren New wrote:
> On 9/9/2011 9:57, Orchid XP v8 wrote:
>> Well, yes, I was referring to the only architecture in existence that
>> people are likely to be writing desktop applications for. :-P
>
> I think even amongst Intel and AMD x64 and x86 architectures, this
> varies.
It probably varies on things like the Atom and other embedded stuff.
> I'm pretty sure it's not 100% automatic or there wouldn't be
> instructions for causing it to happen.
There are instructions for loading stuff without caching it, in case you
happen to know that you're only going to access it once. There are
instructions for flushing the cache, if you're about to do a context
switch or you're controlling memory-mapped hardware. But as far as I
know, you don't have to do anything special to get correct
multi-processor behaviour. (Think about it; if you did, every
multi-threaded application ever written would suddenly break when run on
a multi-chip or multi-core setup.)
>> I saw a paper a while back about how Google (I forget which center)
>> translated part of the monitoring system from Python to Haskell, and
>> documented what they did and didn't find beneficial about this.
>
> Ah. Well, there's monitoring out the wazoo here, so I'm quite certain
> they didn't rewrite even a majority of it.
Oh, I'm sure they only translated one system. And it was only Google
Netherlands (or somewhere like that), not the entire company. (Although
it's surprising that different branches would actually do things
differently...)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/12/2011 1:13, Invisible wrote:
> (Think about it; if you did, every multi-threaded application ever written
> would suddenly break when run on a multi-chip or multi-core setup.)
Not really. You have no more likelihood of breaking because of lack of
memory barriers than you have of breaking because you've cached something in
a register during a task switch.
The compiler just has to write memory barrier instructions out when you
access a volatile variable. That's why the keyword is there.
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 12/09/2011 11:49 PM, Darren New wrote:
> On 9/12/2011 1:13, Invisible wrote:
>> (Think about it; if you did, every multi-threaded application ever
>> written
>> would suddenly break when run on a multi-chip or multi-core setup.)
>
> Not really. You have no more likelihood of breaking because of lack of
> memory barriers than you have of breaking because you've cached
> something in a register during a task switch.
>
> The compiler just has to write memory barrier instructions out when you
> access a volatile variable. That's why the keyword is there.
If you cache something in a register that you shouldn't have, your
application will break on a uniprocessor system. And you'll notice this,
and fix it.
If the hardware didn't enforce cache coherence, applications would work
perfectly on a uniprocessor and then break spectacularly on a
multiprocessor. This doesn't happen, ergo the hardware is enforcing
cache coherence.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/13/2011 1:31, Invisible wrote:
> If you cache something in a register that you shouldn't have, your
> application will break on a uniprocessor system. And you'll notice this, and
> fix it.
Right.
> If the hardware didn't enforce cache coherence, applications would work
> perfectly on a uniprocessor and then break spectacularly on a
> multiprocessor.
In what way would it break, given the OS inserts a memory barrier when it
switches tasks?
I.e., in what case would you expect a variable written to memory followed
immediately by a nondeterministic task switch to give you different results
on a multi vs uni processor? In what case would you expect a variable cached
in a register to give you different results during a task switch on a multi
vs uni processor?
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> If the hardware didn't enforce cache coherence, applications would work
>> perfectly on a uniprocessor and then break spectacularly on a
>> multiprocessor.
>
> In what way would it break, given the OS inserts a memory barrier when
> it switches tasks?
It's not about task switches, it's about two tasks running on different
cores trying to communicate through memory. If the cores didn't
automatically synchronise their caches, that wouldn't work at all.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/14/2011 1:56, Invisible wrote:
> It's not about task switches, it's about two tasks running on different
> cores trying to communicate through memory. If the cores didn't
> automatically synchronise their caches, that wouldn't work at all.
You're missing my point. If it doesn't work with two cores, it doesn't work
with one core either.
If it's automatic, why do x86 CPUs have memory fence instructions?
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 14/09/2011 05:48 PM, Darren New wrote:
> On 9/14/2011 1:56, Invisible wrote:
>> It's not about task switches, it's about two tasks running on different
>> cores trying to communicate through memory. If the cores didn't
>> automatically synchronise their caches, that wouldn't work at all.
>
> You're missing my point. If it doesn't work with two cores, it doesn't
> work with one core either.
Yes it does. Because if two tasks run on the same core, they share the
same cache. It's not possible to have two caches out of sync unless
there's actually, you know, *two caches*.
> If it's automatic, why do x86 CPUs have memory fence instructions?
I'm guessing that's for performance, not correctness.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/14/2011 13:54, Orchid XP v8 wrote:
>> If it's automatic, why do x86 CPUs have memory fence instructions?
> I'm guessing that's for performance, not correctness.
http://software.intel.com/en-us/forums/showthread.php?t=65071
It appears at first google that you are correct. On second google,
http://siyobik.info/main/reference/instruction/LFENCE
I think what's happening is that I might write instructions that store
things out of order, so I store something in a memory address, then store a
pointer to that address some place you will look. On the x86 at least, the
memory fence is necessary to make sure that I have stored the data before I
have stored the pointer to it. You will always fetch the most recent pointer
I have stored, but executing "store data ; store pointer" might store the
pointer before the data without a fence. So it's not caches of main memory
but caches of instruction results that's the issue I was thinking of.
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
