Random permutations in linear time?
Mark
time in Haskell, I noticed that the problem had come up here before
(way back in 1993) and no good solution was posted.
It seems like I've come up with a solution and thought I'd post it
here for criticism and just to share. The following program
implements and demos my solution:
---
import Data.Array
permute elements positions =
let array = (listArray (0, length elements) elements) in
let permute' [] = []
permute' (p:ps) = (array ! p) : (permute' ps) in
permute' positions
main = print (permute elements positions)
where elements = "ABCDEF"
positions = [0,5,1,4,2,3]
---
Of course, this didn't end up helping me much because I've yet to come
up with a good (and fast) way of generating the random positions.
<sigh>
Mark
Tomasz Zielonka
> Of course, this didn't end up helping me much because I've yet to come
> up with a good (and fast) way of generating the random positions.
*This* is the hard part. I am afraid you solved a non-problem ;)
><sigh>
>
> Mark
Best regards,
Tom
--
.signature: Too many levels of symbolic links
Torben Ægidius Mogensen
That is the hard part.
The general problem is to make a function that takes a list of N
elements and a number p between 0 and N!-1 and returns different
permutations of the N elements for different values of p.
If you have mutable arrays, this is easy to do in linear time
(assuming constant-time arithmetic):
permute 1 xs 0 = [xs!0]
permute n xs p
= let i = p `mod` n
p1 = p `div` n
x = xs!i
in
(xs!i := xs!(n-1); x : permute (n-1) xs p1)
The first parameter is the number n of elements, held in the n first
elements of xs.
The problem is to do it in linear time without mutable arrays. Note
that you don't have to implement exactly the above function, as long
as different values of p give different permutations. In other words,
you are allowed to number the permutations differently.
Torben
Mark
Tomasz Zielonka <t.zie...@zodiac.mimuw.edu.pl> wrote in message news:<slrnc0f4ap.2...@zodiac.mimuw.edu.pl>...
> *This* is the hard part. I am afraid you solved a non-problem ;)
And I can't tell you how much this is bothering me. I can do this
*very* easily in almost any imperative language and have it run O(n).
(Infact, one summer long ago, I implemented it in C to figure out
sport teams for an elementary school.) However, I can't come up with
an O(n) implementation in a functional language.
I'm not sure what the implications are if functional languages can't
express solutions that run in asymptotically the same time as in
imperative languages, but they can't be good. Surely, this problem
doesn't really exist...
(And for the above, and any conversation that may follow, lets assume
that array access is O(1), because on my machine it is (at least in
imperative languages).)
Mark
Joachim Durchholz
>
> And I can't tell you how much this is bothering me. I can do this
> *very* easily in almost any imperative language and have it run O(n).
I think it's impossible to do better than O (N log N), at least if the
algorithm is to keep any resemblance with Knuth's.
The reasoning (quite handwavy) is as follows:
The permutation is constructed stepwise, nailing down the permuted
sequence element by element.
This means that the set of items to be considered in the next round has
one arbitrary element removed. I simply know of no functional data
structure that can do this sort of update with O (1) complexity.
("Update" in the functional sense, i.e. without overwriting existing data.)
I'd say that any attempt at doing a random permutation functionally will
have to do it "all at once".
In other words, there must not be intermediate results (which are
difficult to represent), the state of the permutation must be entirely
kept on the stack.
Here's an algorithm:
1) Build a binary tree, with the leaf nodes representing the list
elements. This tree will have, at worst, a total node count of (2N - 1),
so this is O (N).
2) Traverse all nodes. Swap the left and right subtree in each node with
a 50% chance. Since there are at most (N - 1) inner nodes in the tree,
this is O (N), too.
3) Traverse the leaves of the new tree and build the permuted list. This
is O (N) by the same argument as in step (1).
Of course, this can be heavily optimized. Steps (1) and (2) can be
merged, and we can rebuild the algorithms as a single traversal through
the list, keeping a list that represents just the current path from the
tree's root to the current leaf node. Space usage will be N for the
output list, and log N for the path list.
The algorithm doesn't handle lists with a length other than a power of
two, but the extension should be straightforward (just use dummy nodes,
inserting them on tree construction and skipping them on permuted-list
construction).
I hope I don't have any serious blunders in the above algorithm sketch...
> (And for the above, and any conversation that may follow, lets assume
> that array access is O(1), because on my machine it is (at least in
> imperative languages).)
Let's also assume that generating a random number is O (1).
It seems that in reality it's unbounded. At least I can say that all
sources of randomness that I know make take an arbitrary time until they
will return the next unbiased random value. With the exception of
pseudo-random number generators, there's an upper limit related to the
cycle length - which is something that must be increased as soon as it
enters into practical considerations...
Regards,
Jo
--
Currently looking for a new job.
Tomasz Zielonka
>
> Here's an algorithm:
> 1) Build a binary tree, with the leaf nodes representing the list
> elements. This tree will have, at worst, a total node count of (2N - 1),
> so this is O (N).
> 2) Traverse all nodes. Swap the left and right subtree in each node with
> a 50% chance. Since there are at most (N - 1) inner nodes in the tree,
> this is O (N), too.
> 3) Traverse the leaves of the new tree and build the permuted list. This
> is O (N) by the same argument as in step (1).
Maybe I am overlooking something, but I think that for input
1 2 3 4
you won't be able to generate
1 3 2 4
assuming your tree initially looks like:
+
/ \
/ \
+ +
/ \ / \
1 2 3 4
To get this combination you would have to do something more, for example
rotations
+
/ \
/ \
1 +
/ \
/ \
2 +
/ \
3 4
and then
+
/ \
/ \
1 +
/ \
/ \
+ 4
/ \
2 3
You can achieve every permutation doing rotations and swaps, but then
your algorithm is no longer linear, and I don't know what probabilities
to take for rotations.
Joachim Durchholz
> Joachim Durchholz wrote:
>
>>Here's an algorithm:
>>1) Build a binary tree, with the leaf nodes representing the list
>>elements. This tree will have, at worst, a total node count of (2N - 1),
>>so this is O (N).
>>2) Traverse all nodes. Swap the left and right subtree in each node with
>>a 50% chance. Since there are at most (N - 1) inner nodes in the tree,
>>this is O (N), too.
>>3) Traverse the leaves of the new tree and build the permuted list. This
>>is O (N) by the same argument as in step (1).
>
>
> Maybe I am overlooking something, but I think that for input
>
> 1 2 3 4
>
> you won't be able to generate
>
> 1 3 2 4
You're right. I can get an equal probability for any item on any place,
but I don't get an equal probability for every permutation.
Well, it was a nice concept :-)
Joachim Durchholz
> However, I can't come up with an O(n) implementation in a functional
> language.
Here's another stab at the problem. I should have looked into the books
right at the first time, that's easier than trying to reinvent the wheel :-)
The main problem is insertion into a sequence at an arbitrary position.
Looking into Okasaki's "Purely Functional Data Structures", I note that
insertion in binomial heaps (aka binomial priority queues) runs in
amortized O (1) time. This is exactly what's needed: inserting N
elements into an empty tree is exactly the situation where amortized
bounds are relevant :-)
So the algorithm is simple: insert the items in a random order, then
transform the queue into a linear list.
Notes:
1) Binomial heaps consist of subtrees, each the node count of each
subtree being an exact power of two. Which means that it's relatively
easy to associate the proper probabilities.
2) Shuffling doesn't go by a fixed order function but by randomness. I'd
be interested to hear whether it's possible to organize the code for the
binomial heaps so that it will accept a fixed ordering function in the
same way as a random number generator monad. (If that's impossible, it
would be necessary to re-implement binomial trees for randomness, and I
don't particularly like this kind of dumb rewrite. Unfortunately, I
don't write functional code on a day-to-day basis, so I'm lacking the
practical experience to determine this for myself :-((( )
Sam Lindley
"Torben Ægidius Mogensen" <tor...@diku.dk> wrote in message
news:w5d69kr...@pc-032.diku.dk...
> mf...@cpsc.ucalgary.ca (Mark) writes:
>
> > In trying to come up with a way to do random permutations in linear
> > time in Haskell, I noticed that the problem had come up here before
> > (way back in 1993) and no good solution was posted.
> >
> > It seems like I've come up with a solution and thought I'd post it
> > here for criticism and just to share. The following program
> > implements and demos my solution:
> >
> > ---
> > import Data.Array
> >
> > permute elements positions =
> > let array = (listArray (0, length elements) elements) in
> > let permute' [] = []
> > permute' (p:ps) = (array ! p) : (permute' ps) in
> > permute' positions
> >
> > main = print (permute elements positions)
> > where elements = "ABCDEF"
> > positions = [0,5,1,4,2,3]
> > ---
> >
> > Of course, this didn't end up helping me much because I've yet to come
> > up with a good (and fast) way of generating the random positions.
>
> That is the hard part.
>
> The general problem is to make a function that takes a list of N
> elements and a number p between 0 and N!-1 and returns different
> permutations of the N elements for different values of p.
Ah... when you say linear time you mean linear in N, but (being pedantic)
the problem you state has an input which is considerably bigger than N. In
fact the most efficient encoding of the input has size O(N log N). So an O(N
log N) algorithm is linear in the size of the input :-) It's easy to see
that this is also a lower bound: it must take at least O(N log N) steps to
read the input.
> If you have mutable arrays, this is easy to do in linear time
> (assuming constant-time arithmetic):
But arithmetic operations aren't really (asymptotically) constant time. In
the best case they are logarithmic. Of course, in practical applications
it's usually perfectly reasonable to assume that arithmetic operations are
constant time, given that they are more-or-less constant time for numbers up
to 32-bits (or whatever the word size of the architecture is). In contrast,
although the relevant operations on trees can be performed in logarithmic
time, the actual difference in speed between different sizes of tree is
noticeable in practice, even for small trees.
> permute 1 xs 0 = [xs!0]
> permute n xs p
> = let i = p `mod` n
> p1 = p `div` n
> x = xs!i
> in
> (xs!i := xs!(n-1); x : permute (n-1) xs p1)
>
> The first parameter is the number n of elements, held in the n first
> elements of xs.
>
> The problem is to do it in linear time without mutable arrays. Note
> that you don't have to implement exactly the above function, as long
> as different values of p give different permutations. In other words,
> you are allowed to number the permutations differently.
Sam
Sam Lindley
>
> > In trying to come up with a way to do random permutations in linear
> > time in Haskell, I noticed that the problem had come up here before
> > (way back in 1993) and no good solution was posted.
> >
> > It seems like I've come up with a solution and thought I'd post it
> > here for criticism and just to share. The following program
> > implements and demos my solution:
> >
> > ---
> > import Data.Array
> >
> > permute elements positions =
> > let array = (listArray (0, length elements) elements) in
> > let permute' [] = []
> > permute' (p:ps) = (array ! p) : (permute' ps) in
> > permute' positions
> >
> > main = print (permute elements positions)
> > where elements = "ABCDEF"
> > positions = [0,5,1,4,2,3]
> > ---
> >
> > Of course, this didn't end up helping me much because I've yet to come
> > up with a good (and fast) way of generating the random positions.
>
> That is the hard part.
>
> The general problem is to make a function that takes a list of N
> elements and a number p between 0 and N!-1 and returns different
> permutations of the N elements for different values of p.
Ah... when you say linear time you mean linear in N, but (being pedantic)
the problem you state has an input which is considerably bigger than N. In
fact the most efficient encoding of the input has size O(N log N). So an O(N
log N) algorithm is linear in the size of the input :-) It's easy to see
that this is also a lower bound: it must take at least O(N log N) steps to
read the input.
> If you have mutable arrays, this is easy to do in linear time
> (assuming constant-time arithmetic):
But arithmetic operations aren't really (asymptotically) constant time. In
the best case they are logarithmic. Of course, in practical applications
it's usually perfectly reasonable to assume that arithmetic operations are
constant time, given that they are more-or-less constant time for numbers up
to 32-bits (or whatever the word size of the architecture is). In contrast,
although the relevant operations on trees can be performed in logarithmic
time, the actual difference in speed between different sizes of tree is
noticeable in practice, even for small trees.
> permute 1 xs 0 = [xs!0]
> permute n xs p
> = let i = p `mod` n
> p1 = p `div` n
> x = xs!i
> in
> (xs!i := xs!(n-1); x : permute (n-1) xs p1)
>
> The first parameter is the number n of elements, held in the n first
> elements of xs.
>
> The problem is to do it in linear time without mutable arrays. Note
> that you don't have to implement exactly the above function, as long
> as different values of p give different permutations. In other words,
> you are allowed to number the permutations differently.
Sam
Joachim Durchholz
> But arithmetic operations aren't really (asymptotically) constant
> time. In the best case they are logarithmic. Of course, in practical
> applications it's usually perfectly reasonable to assume that
> arithmetic operations are constant time, given that they are
> more-or-less constant time for numbers up to 32-bits (or whatever the
> word size of the architecture is).
Now, this all is really pedantic.
In practice, we're interested how the algorithm behaves, independently
of the efficiency of the encodings it uses. So we're making all sorts of
unwarranted assumptions: that arithmetic is constant-time, that
random-number generation is constant-time, that memory is infinite (but
we have a memory hierarchy in practice, from L1 cache down to virtual
memory on disk), etc. etc.
Tomasz Zielonka
>
> The main problem is insertion into a sequence at an arbitrary position.
> Looking into Okasaki's "Purely Functional Data Structures", I note that
> insertion in binomial heaps (aka binomial priority queues) runs in
> amortized O (1) time. This is exactly what's needed: inserting N
> elements into an empty tree is exactly the situation where amortized
> bounds are relevant :-)
Are you claiming that you can sort N elements using comparisons in O(N)
time?
Binomial heap's insert's amortized cost is O(1), but delete-min's is
O(log N).
Tomasz Zielonka
Not, it's not that pedantic. If we talk about numbering permutations,
32-bits will suffice only up to 12!, and 64-bits only up to 20!.
For N <= 20 we could as well say that all algoritms are O(1).
You have to use arbitrary size arithmetic with not so constant-time
operations.
Marcin 'Qrczak' Kowalczyk
> Not, it's not that pedantic. If we talk about numbering permutations,
> 32-bits will suffice only up to 12!, and 64-bits only up to 20!.
>
> For N <= 20 we could as well say that all algoritms are O(1).
But we don't need to perform arithmetic on serial numbers of permutations,
only on element indices. So in practice it's linear up to N being comparable
to available memory (the main memory is slower than L1 or L2 cache only by
a constant factor).
Theoretical complexity considerations really don't tell the whole story
here.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Tomasz Zielonka
> On Sat, 17 Jan 2004 09:01:55 +0000, Tomasz Zielonka wrote:
>
>> Not, it's not that pedantic. If we talk about numbering permutations,
>> 32-bits will suffice only up to 12!, and 64-bits only up to 20!.
>>
>> For N <= 20 we could as well say that all algoritms are O(1).
>
> But we don't need to perform arithmetic on serial numbers of permutations,
> only on element indices. So in practice it's linear up to N being comparable
> to available memory (the main memory is slower than L1 or L2 cache only by
> a constant factor).
>
> Theoretical complexity considerations really don't tell the whole story
> here.
Aren't we talking about Torben's problem?
The general problem is to make a function that takes a list of N
elements and a number p between 0 and N!-1 and returns different
permutations of the N elements for different values of p.
If you have mutable arrays, this is easy to do in linear time
(assuming constant-time arithmetic):
Best regards,
Joachim Durchholz
> Joachim Durchholz wrote:
>
>>The main problem is insertion into a sequence at an arbitrary position.
>>Looking into Okasaki's "Purely Functional Data Structures", I note that
>>insertion in binomial heaps (aka binomial priority queues) runs in
>>amortized O (1) time. This is exactly what's needed: inserting N
>>elements into an empty tree is exactly the situation where amortized
>>bounds are relevant :-)
>
> Are you claiming that you can sort N elements using comparisons in O(N)
> time?
>
> Binomial heap's insert's amortized cost is O(1), but delete-min's is
> O(log N).
You're right.
That's a suggestion for the next revision of Chris Okasaki's book: give
complexities for all algorithms, in a table :-)
Anyway. There's no way that any functional variant of shuffling is as
fast as the mutable array version, even if it's O (1).
Personally, I'd call it a day and write a referentially transparent
function that uses the array just internally. That way, you keep all the
nice properties of functional languages without sacrificing efficiency.
Tomasz Zielonka
> I'm not sure what the implications are if functional languages can't
> express solutions that run in asymptotically the same time as in
> imperative languages, but they can't be good. Surely, this problem
> doesn't really exist...
Impure functional languages don't have this problem, because... they are
impure and they provide imperative arrays.
Most general purpose purely functional languages also allow you to write
imperative code, but in a restricted way that doesn't affect purity of
pure code. In Haskell and Clean you can encapsulate this imperative
algorithm in a function that has a pure interface.
As you can see, this is not that big problem.
BTW, this restricted imperative programing can be even nicer than
unrestricted IP.
Joachim Durchholz
> I'm not sure what the implications are if functional languages can't
> express solutions that run in asymptotically the same time as in
> imperative languages,
Purely functional languages cannot express everything in the same
complexity as imperative languages. Shuffling may indeed be one of those
cases.
The good news is that big-Oh complexity doesn't degrade by more than a
factor of log N. (That's because mutable arrays can be simulated using a
log N algorithm.)
In practice, these differences are less relevant. O (log N) grows so
slowly that, for all intents and purposes, it amounts to the same as
O (1) - any N for which the difference would become noticeable would far
exceed the number of bits in all computers of the world.
Or, put another way: when it comes to optimizing an O (N log N)
algorithm, I'd put more effort into reducing the constant factors than
into eliminating the log N factor. (Mostly because getting rid of log N
would probably require an entirely different algorithm, while
eliminating constant factors can be done incrementally *g*)
> but they can't be good.
Efficiency is just one factor in the quality of a language or a
paradigm. A slowdown by a small constant factor or a loss of O (log N)
isn't very important - and functional languages, if implemented and used
with a reasonable level of expertise, aren't worse than that.
When programs become large, things get more interesting. The good news
is that functional programs scale better: they are easier to maintain,
easier to analyse. Part of this effect is that functional languages can
abstract things that cannot (typically) be abstracted in imperative
languages: loops, iterating over various kinds of containers in various
ways, etc. Imperative languages can do similar things, but they require
far more syntactic overhead. In other words, you can achieve the same
thing with far less syntactic overhead (if you have a function that will
iterate over a container for you, you don't need an iterator variable
that you'd have to declare, initialize, increment, and check for
fencepost errors). Which leads us to the conclusion that functional
languages require far less lines of code to achieve the same things, so
the functional program is more maintainable simply because it's shorter.
(There are other things that improve maintainability as well: side
effects can form implicit communication channels between modules, and
that makes modifying large imperative systems more difficult. In
functional programs, no side effects exist, so you can go about
modifying the behaviour of the software with far better confidence in
having covered all effects of your change, which means you have less
test cases to check and/or less bugs to fix.)
Søren Debois
> Purely functional languages cannot express everything in the same
> complexity as imperative languages.
I'd like a reference for this?
--
--- Debois
Adrian Hey
> Anyway. There's no way that any functional variant of shuffling is as
> fast as the mutable array version, even if it's O (1).
and later
> Purely functional languages cannot express everything in the same
> complexity as imperative languages. Shuffling may indeed be one of those
> cases.
Eeek! Danger.. FUD alert!
Sorry if I appear rude, but this is the kind of stuff certain ignorant
people in this world might start parroting if it goes unchallenged.
If it's true then FP really does have a problem.
I think you're wrong though (fortunately :-)
It's true that (by and large) FP'ers prefer problem solutions using lists,
trees etc, because they're more flexible and reasoning about them is often
easier than reasoning about arrays (especially mutable arrays). It's also
true that (by and large) current FPL compilers don't do a particularly good
job at dealing with arrays efficiently. But there is absolutely no reason
that I can see why this need be so, and there are been some notable
exceptions (like Sisal,Sac).
Personally, if I was interested (in fact I am:-) in designing a language
for fast array processing, I would still make it a pure FPL. If anything
I think I'd make life harder for myself by including imperative features
(explicitly mutable state).
As I remarked in a previous post, there's no law that says *executables*
generated by FPL compilers can't use destructive overwrites, mutable
arrays etc..
If the imperative version relies on constant time array read/writes
this can be supported in many pure FPLs, even as they are today.
For example..
In Clean you can use uniqueness typing
In Haskell you can use DiffArrays, or the ST monad (pseudo imperative
programming).
In <any FPL> the compiler could (in principle) generate decent code
without the aid of any programmer annotation or "cues" (though I
suspect most don't right now wrt using destructive array updates).
Also, I don't think that FP'ers can really get away with claiming
that the difference between O(1) imperative operations and O(log N)
"purely functional" operations is negligible (if you consider the
difference between destructively updating an unboxed array element or
non-destructively inserting a new value in a tree say).
Regards
--
Adrian Hey
Peter Van Roy
> Which leads us to the conclusion that functional
> languages require far less lines of code to achieve the same things, so
> the functional program is more maintainable simply because it's shorter.
So what about a language that is both functional and has mutable state
as well, where you can use the state in exactly those places where it is
needed? Logically, it can't be worse than a purely functional language,
since you can always restrict yourself to the purely functional subset.
It can only be better.
Peter
PS: I know about monads and they are not equivalent to mutable state.
They lack important modularity properties of mutable state.
Tomasz Zielonka
> PS: I know about monads and they are not equivalent to mutable state.
> They lack important modularity properties of mutable state.
Could you be more precise?
Best regards,
Tomasz
Vincenzo aka Nick Name
>
> So what about a language that is both functional and has mutable state
> as well, where you can use the state in exactly those places where it is
> needed?
Well, don't many hybrid languages like ocaml act like this?
V.
Joachim Durchholz
> As I remarked in a previous post, there's no law that says *executables*
> generated by FPL compilers can't use destructive overwrites, mutable
> arrays etc..
Of course not.
But getting the compiler to optimize everything out so that it's as fast
as an imperative language is a difficult goal. Even the OCaml people
don't claim that OCaml beats C (and those programs that came out best in
the ICFP contests made heavy use of OCaml's impure features, as mutable
arrays).
I think one can safely say that, on the average, FPL compilers generate
slower code that imperative-language compilers. To avoid being FUDdy one
should also add that even the least optimizing FPL compilers will beat
JVM and .net interpreted code, hands down, every time :-)
> If the imperative version relies on constant time array read/writes
> this can be supported in many pure FPLs, even as they are today.
> For example..
> In Clean you can use uniqueness typing
> In Haskell you can use DiffArrays, or the ST monad (pseudo imperative
> programming).
> In <any FPL> the compiler could (in principle) generate decent code
> without the aid of any programmer annotation or "cues" (though I
> suspect most don't right now wrt using destructive array updates).
Well, in principle, the compiler could also do near-perfect strictness
analysis and heaps of other things.
There's always the issue of how much work went into the compilers. At
comparable effort, imperative languages will be smaller. So what? The
differences become negligible (and are negligible even today).
> Also, I don't think that FP'ers can really get away with claiming
> that the difference between O(1) imperative operations and O(log N)
> "purely functional" operations is negligible (if you consider the
> difference between destructively updating an unboxed array element or
> non-destructively inserting a new value in a tree say).
I think we can. YMMV.
A well-written O (N log N) program will beat any badly-written O (N)
program, hands down, unless the O (N log N) program has to set up lots
of data structures or other large-scale penalties.
In other words: getting rid of the log N factor in a functional version
of shuffling will solve the problem only very partially. Unless the
functional version is some simulation of array updates, with a compiler
that is smart enough to implement it using a mutable array, the
functional version will still generate and destroy list nodes where the
array version doesn't, and since the array shuffling is very fast, I
don't think a functional version can really attain that speed.
That's no FUD, that's simply the state of affairs. Functional
programmers do tend to use lists and trees where imperative programmers
use arrays. Arrays are faster unless you need insertion; shuffling is an
operation that doesn't need insertion; so the array version is faster.
Arrays are alien to most functional programmers' style, so their version
will be slower.
I don't see much debatable in such statement. The danger of being
misquoted is always there, but you don't have to search this newsgroup
to get any type of misquotable statements.
(Though I am indeed flattered that you consider my statements
influential enough that they should be corrected. *eg*)
Joachim Durchholz
Sorry, no.
I thought I had something in mind, but when I looked, the URL was gone,
and I don't have any other references handy.
Anybody else? I'm pretty sure there are hard proofs for such a
statement, but I can't come up with one.
Ben Rudiak-Gould
>Tomasz Zielonka <t.zie...@zodiac.mimuw.edu.pl> wrote in message news:<slrnc0f4ap.2...@zodiac.mimuw.edu.pl>...
>> *This* is the hard part. I am afraid you solved a non-problem ;)
>
>And I can't tell you how much this is bothering me. I can do this
>*very* easily in almost any imperative language and have it run O(n).
>[...] However, I can't come up with an O(n) implementation in a
>functional language.
>
>I'm not sure what the implications are if functional languages can't
>express solutions that run in asymptotically the same time as in
>imperative languages, but they can't be good. Surely, this problem
>doesn't really exist...
It doesn't, because factors of log n are a chimera. This issue just
came up in the "Perfect list shuffling" thread of a few days ago, but
I think it deserves further elaboration.
Let's look at the usual Theta(n) imperative algorithm:
for i <- n-1 downto 1:
j <- random() % (i+1)
swap Array[i], Array[j]
The loop runs Theta(n) times, and each time a random number is
produced and a couple of array locations are read and written --
presumably constant-time operations all. Or are they?
Let's set the array access aside for a moment and look at the random
numbers. It's easy to see that a perfect (or reasonably near-perfect)
shuffle requires at least log_2(n!) ~ (n log_2 n) bits of randomness;
otherwise it can't even produce every possible permutation of its
input, much less in equal proportions. Any shuffling algorithm is
necessarily Theta(n log n) or worse for this reason alone.
So why does the imperative algorithm seem to be Theta(n)? Because it
_wastes bits_. If n is 256, then the first iteration through the loop
will generate (probably) 32 bits of randomness and essentially throw
away all but eight of them; the second iteration will do similarly. If
n is 2^28, it will throw away fewer of the bits. In this way the
algorithm effectively pads out its runtime to a Theta(n) curve which
is _above_ the natural Theta(n log n) curve that it ought to be
following. It can't keep doing this in the n->infinity limit, but it
can do it for all n < 2^32, and no one will ever pass it anything
higher.
What about array access? Same story. In order to access an element in
an array of size n, you need to send at least log_2(n) address bits
across the address bus to the memory subsystem. Inasmuch as array
(random-)access times are independent of n, it's because unnecessary
extra bits are added to reach a fixed total (like 32).
Real hardware is more complicated than that, however. I'm not a
hardware person, but I think that modern protocols involve first
selecting a memory "bank" (high bits) and then requesting locations
within that bank (low bits) as long as the bank remains the same.
Intermediate cache memories work in a similar way. The more you
fine-tune this system by adding cache tiers or sub-sub-banks, the more
array (random-)access times will approach their natural Theta(log n)
curve. With fewer tiers, the access times zig-zag around that curve,
having large regions (one per tier) in which they appear to be
Theta(1), separated by areas of rapid growth. In the end, the
Theta(log n) curve wins out -- there's no way to avoid it.
"But," you say, "Theta(n log n) functional algorithms *are* slower."
They are, but that's because the _constant factor_ is larger. It's
larger in large part because functional languages have to simulate a
deep-recursive environment on top of machines which have been
optimized out the wazoo for iterative access patterns. An incredible
amount of research has gone into this optimization, and it would
probably take decades of similar investment to get the same kind of
performance out of functional designs. Almost every aspect of the
computer's architecture would have to be redesigned. On such a
machine, current pseudo-Theta(n) algorithms would be Theta(n log n),
and current Theta(n log n) algorithms would have much lower constant
factors.
Moral: forget about finding a Theta(n) algorithm, and concentrate
instead on finding an algorithm which is fast enough for the range of
values of n that you care about. Write it in C if you have to --
there's no shame in that.
-- Ben
Joachim Durchholz
>
> Let's set the array access aside for a moment and look at the random
> numbers. It's easy to see that a perfect (or reasonably near-perfect)
> shuffle requires at least log_2(n!) ~ (n log_2 n) bits of
> randomness; otherwise it can't even produce every possible
> permutation of its input, much less in equal proportions. Any
> shuffling algorithm is necessarily Theta(n log n) or worse for this
> reason alone.
That's an intriguing thought!
> Real hardware is more complicated than that, however. I'm not a
> hardware person, but I think that modern protocols involve first
> selecting a memory "bank" (high bits) and then requesting locations
> within that bank (low bits) as long as the bank remains the same.
That's not necessarily true.
> Intermediate cache memories work in a similar way. The more you
> fine-tune this system by adding cache tiers or sub-sub-banks, the
> more array (random-)access times will approach their natural
> Theta(log n) curve.
That is only true if memory sizes are increasing exponentially while
access times are increasing sub-exponentially.
Since typical hierarchies have less than a handful of levels, it's
unlikely that anything substantial can be said about that.
One could relate memory size, the volume that it occupies, line length,
and impulse speed to get some bounds on the relationship between memory
size and access time. But real hardware is (still) quite far from these
limits, and harddisks and magnetic tapes are even farther.
> "But," you say, "Theta(n log n) functional algorithms *are* slower."
> They are, but that's because the _constant factor_ is larger.
Agreed.
> It's larger in large part because functional languages have to
> simulate a deep-recursive environment on top of machines which have
> been optimized out the wazoo for iterative access patterns.
I don't think that the language./.CPU mismatch is so large.
Functional languages are implemented using imperative code. Graph
reduction algorithms are even inherently stateful, and the main purpose
of these algorithms is to get more efficient handling of high-order
functions.
Actually it's easier to implement FPLs on the bare metal than on the
various supposedly language-independent platforms, like the JVM, C, or
.net (not entirely sure about the latter one, I heard that FPL
implementors had some say in the design of the VM, but I also heard that
it's still not a perfect marriage).
Also, I don't know of any incremental change in modern CPU design that
would give an immediate benefit to functional languages.
This all doesn't mean that hardware couldn't be more helpful towards
FPLs (I'm not far enough into FPL implementation to say anything like
that), but my feeling is that your assumptions don't hold.
(OO languages definitely have more trouble.)
> Moral: forget about finding a Theta(n) algorithm, and concentrate
> instead on finding an algorithm which is fast enough for the range of
> values of n that you care about. Write it in C if you have to --
> there's no shame in that.
Fully agreed with that.
Torben Ægidius Mogensen
> Adrian Hey wrote:
>
> > As I remarked in a previous post, there's no law that says *executables*
> > generated by FPL compilers can't use destructive overwrites, mutable
> > arrays etc..
>
> Of course not.
> But getting the compiler to optimize everything out so that it's as fast
> as an imperative language is a difficult goal.
The last little constant factor is difficult, true, but compiling an
FL to allow imperative programs using arrays to be translated with
only constant overhead isn't: You can compile arrays in such a way
that at an element update, the new copy of the array is produced by
destructive update, but the old copy goes through a modification list.
This requires an extra indirection for access, and an update requires
creating a heap object and overwriting an indirection.
The effect is that if the array is single-threaded, access and update
are both O(1). Accesses to "old" copies can be slow as you have to
walk through a modification list, but these can be shortcircuited (by
making a new shallow copy of the array) in such a way that all
accesses get O(1) randomized amortized cost. The idea is that
whenever you walk a modification link, you make a copy with
probability 1/N, where N is the size of the array.
All of the above puts some fairly hefty constant factors on running
time, which is why it generally isn't used in compilers for FP's.
Torben
Adrian Hey
> Adrian Hey wrote:
>> As I remarked in a previous post, there's no law that says *executables*
>> generated by FPL compilers can't use destructive overwrites, mutable
>> arrays etc..
>
> Of course not.
> But getting the compiler to optimize everything out so that it's as fast
> as an imperative language is a difficult goal.
Difficult and impossible are very different things.
>> If the imperative version relies on constant time array read/writes
>> this can be supported in many pure FPLs, even as they are today.
>> For example..
>> In Clean you can use uniqueness typing
>> In Haskell you can use DiffArrays, or the ST monad (pseudo imperative
>> programming).
>> In <any FPL> the compiler could (in principle) generate decent code
>> without the aid of any programmer annotation or "cues" (though I
>> suspect most don't right now wrt using destructive array updates).
>
> Well, in principle, the compiler could also do near-perfect strictness
> analysis and heaps of other things.
Well indeed, if something's possible in principle then there's no problem,
long term. What I'm concerned about is the (alleged) impossibility of FPL's
being as efficient as imperative languages for some problems, even in
principle. In another post you imply there exists a hard proof of this.
>> Also, I don't think that FP'ers can really get away with claiming
>> that the difference between O(1) imperative operations and O(log N)
>> "purely functional" operations is negligible (if you consider the
>> difference between destructively updating an unboxed array element or
>> non-destructively inserting a new value in a tree say).
>
> I think we can. YMMV.
MMDV
> A well-written O (N log N) program will beat any badly-written O (N)
> program, hands down, unless the O (N log N) program has to set up lots
> of data structures or other large-scale penalties.
I find this a dubious (well pointless actually) assertion.
You might as well say a well written BASIC program will beat any
sufficiently badly written Haskell program (or vice-versa).
Surely we should be comparing well written solutions in each case.
> In other words: getting rid of the log N factor in a functional version
> of shuffling will solve the problem only very partially. Unless the
> functional version is some simulation of array updates, with a compiler
> that is smart enough to implement it using a mutable array,
Dunno what you mean by a simulation of array updates. The programmers
model is to have an update function which returns a new array. All that
is required (from the programmer at least) to make destructive updates
safe is for the array to be used in the same single threaded manner (as
far as updates are concerned) that would be used in the imperative version
of the algorithm. This is something the compiler can check at compile time.
Admitedly non-stricness may complicate matters in some languages, but not
much AFAICS.
> the
> functional version will still generate and destroy list nodes where the
> array version doesn't, and since the array shuffling is very fast, I
> don't think a functional version can really attain that speed.
Obviously if the program still uses lists (for whatever reason) the
program will be slower. So..?
> That's no FUD, that's simply the state of affairs. Functional
> programmers do tend to use lists and trees where imperative programmers
> use arrays. Arrays are faster unless you need insertion; shuffling is an
> operation that doesn't need insertion; so the array version is faster.
> Arrays are alien to most functional programmers' style, so their version
> will be slower.
> I don't see much debatable in such statement.
What's debatable is whether this has anything to do with functional vs.
imperative. You are essentially comparing two different algorithms, then
(incorrectly IMO) asserting that faster one cannot be implemented
efficiently in a FPL, and it therefore follows that FPL's are forever
doomed to be slower than imperative languages for certain problems.
> The danger of being
> misquoted is always there, but you don't have to search this newsgroup
> to get any type of misquotable statements.
So what are you saying? Sometimes you seem to be saying that the (purely
hypothetical) slowness of FPL's is caused by a mixture of using
traditional FP style and lack of adequate R&D effort in compiler
technology (which may well be true), and sometimes you seem to be saying
that slowness of FPL's for some problems is an unalterable law of nature,
and there exists a hard proof of this.
Regards
--
Adrian Hey
Matthias Blume
Nicholas Pippenger, "Pure versus Impure Lisp", in POPL'96.
Matthias
Matthias Blume
> In Clean you can use uniqueness typing
For some programs the types won't be unique.
> In Haskell you can use DiffArrays, or the ST monad (pseudo imperative
> programming).
AFAIC, using the ST monad *is* imperative programming. The monadic
value represents the computation (which at this point is still in the
state of not having occured). Only the manipulation of monadic values
is pure, the execution of the computation represented by the final
value is imperative in nature.
Matthias
Darius
Matthias Blume
No doubt. Of course, lazy evaluation makes essential use of
assignment (internally).
Matthias
Darius
Matthias Blume <fi...@my.address.elsewhere> wrote:
> Adrian Hey <ah...@NoSpicedHam.iee.org> writes:
>
> > In Clean you can use uniqueness typing
>
> For some programs the types won't be unique.
So? Force them to be. At any rate, if you have a threaded unique and
therefore imperatively updateable array, you can call that "memory".
Lookup and update are constant-time and you can therefore simulate any
imperative program with the same complexity.
Albert Lai
> Arrays are alien to most functional programmers'
> style, so their version will be slower.
> I don't see much debatable in such statement.
Are we back to this "the 'natural' programming style in paradigm X
gives a less efficient algorithm than the 'natural' style in Y"
assertion? I thought I just saw one such debate over the past two
weeks.
Joachim Durchholz
> Joachim Durchholz <joachim....@web.de> writes:
>
>> Arrays are alien to most functional programmers' style, so their
>> version will be slower. I don't see much debatable in such
>> statement.
>
> Are we back to this "the 'natural' programming style in paradigm X
> gives a less efficient algorithm than the 'natural' style in Y"
> assertion?
My experience is that languages encourage certain idioms, and the least
common denominator for FPLs seems to be "lots of list processing, with
increasing usage of higher-order functions as experience grows".
If your personal experience differs, I'd be glad to see reports -
experience reports help us all along to form a more accurate picture of
reality.
> I thought I just saw one such debate over the past two weeks.
A debate won't help if personal experience is available.
And I'll grant any day that your personal experience is richer than mine :-)
Tomasz Zielonka
>
> My experience is that languages encourage certain idioms, and the least
> common denominator for FPLs seems to be "lots of list processing, with
> increasing usage of higher-order functions as experience grows".
Experienced programmer will use the most idiomatic datatypes in the
beginning, but will consider switching to other datatypes if there are
performance problems.
For example, I often use GHC's immutable unboxed arrays for performance
sensitive programs, specifically for dealing with binary data formats. I
can also use lists - the code is overloaded on the monad that does the
parsing and I have two implementations for such monad, one using Parsec
(lists) and one using unboxed arrays. The latter is up to 30 times
faster.
Designing parsers in this way I was able to use list based parser
initially and then switching to the array based parser almost without
touching the code using the parser.
Joachim Durchholz
> Joachim Durchholz wrote:
>
>> Adrian Hey wrote:
>>
>>> As I remarked in a previous post, there's no law that says
>>> *executables* generated by FPL compilers can't use destructive
>>> overwrites, mutable arrays etc..
>>
>> Of course not. But getting the compiler to optimize everything out
>> so that it's as fast as an imperative language is a difficult goal.
>
> Difficult and impossible are very different things.
"Difficult" in the sense of "undecidable". I was understating the point
a bit.
Of course, a lot can be done via heuristics. And optimizing an
imperative language touches many undecidable issues as well.
It's just that many things are exceedingly difficult to do, to the point
that they become indistinguishable from impossible. Many people have
claimed that one of the strengths of FPLs is that the compiler can
better reason about the code, but the "fastest" language around is
OCaml, which has been reported as "we just use a solid machine code
generation backend". Strictness analysis seems to be the frontier that
Haskell compilers and developers spend most of their time (or,
conversely, little amount of strictness analysis accounts for loss of
run-time efficiency). The same goes for uniqueness analysis (or whatever
you name the analysis to check whether some data object can be reused).
I haven't implemented any FPL compiler; my main source of information
for these issues is reports in this newsgroup (and the occasional white
paper and research report). The previous paragraph is a summary of what
I have been reading.
If that's FUD, then it was originally distributed by the language
implementers.
If it's wrong, please correct it - I'm always happy to learn.
>>> If the imperative version relies on constant time array
>>> read/writes this can be supported in many pure FPLs, even as they
>>> are today. For example.. In Clean you can use uniqueness typing
>>> In Haskell you can use DiffArrays, or the ST monad (pseudo
>>> imperative programming). In <any FPL> the compiler could (in
>>> principle) generate decent code without the aid of any programmer
>>> annotation or "cues" (though I suspect most don't right now wrt
>>> using destructive array updates).
>>
>> Well, in principle, the compiler could also do near-perfect
>> strictness analysis and heaps of other things.
>
> Well indeed, if something's possible in principle then there's no
> problem, long term.
Erm... long-term feasibility (sp?) issues don't impress me much, sorry.
If FPL implementation (and corresponding language design) can improve,
then they can in the imperative arena just as well.
Just look at Fortran - it's still alive, and not going to be replaced by
a better language, simply because language definition and compiler
technology have been improved over more decades than those of its
competition.
Arguing long-term improvements runs a high risk of getting stuck in the
same situation as C/Pascal/C++ are wrt. Fortran: being the eternal
second-best.
Of course, these languages have been living well in that position. And
that's the point: if there is a disadvantage, there is little point in
denying it, it's more useful to emphasize the advantages. And FPLs have
some quite strong arguments going for them.
> What I'm concerned about is the (alleged) impossibility of FPL's
> being as efficient as imperative languages for some problems, even in
> principle. In another post you imply there exists a hard proof of
> this.
There doesn't seem to be, at least nobody in this group knows one.
As I also said in that post, it's just a dim recollection of a paper
that I read years ago.
>> A well-written O (N log N) program will beat any badly-written O
>> (N) program, hands down, unless the O (N log N) program has to set
>> up lots of data structures or other large-scale penalties.
>
> I find this a dubious (well pointless actually) assertion. You might
> as well say a well written BASIC program will beat any sufficiently
> badly written Haskell program (or vice-versa).
>
> Surely we should be comparing well written solutions in each case.
Assuming "typical usage" (I know how vague that notion is, I'm using it
for lack of a better one), there will be smaller data objects, the
compiler will not be able to reuse memory as an imperative programmer
could, and getting high-level functions to run quickly is difficult too.
Under these conditions, I'd be quite surprised if the functional version
were as fast as the imperative one.
Not that this is too relevant. The functional programmer will be done
earlier, so he has more time to either take on the next project, or to
do some profiling and improve the speed so that it matches (or even
exceeds) that of the imperative program. Even better, the functional
program will most likely be easier to maintain (since functional
languages encourage a more decoupled programming style). With today's
hardware resources, I'll go for an FPL any day, unless I'm programming a
3D graphics engine or similar stuff where you "can't have too much CPU"
(and even then doing it the functional way and optimizing it afterwards
might give me better long-term results).
Note that all of the above only applies up to a certain total size.
Imperative languages begin to suck badly at a given software size:
changes begin to have effects in unexpected areas. Insisting on good
software quality in the seminal phase can help, but only so much (and
often it's not very clear what "good software quality" would be).
Functional software that replaces some imperative software is smaller,
which means less programmer time and less bugs (simply by virtue of a
reduced line count). It makes decoupling easier. This alone should give
functional languages a tremendous advantage once the software grows to
large proportions (I'm speaking about dozens-of-personyears projects here).
This aspect is far more relevant than any constant factors and O (log N)
complexities.
(BTW the term "well written" that you were using is quite vague, too.
Language efficiency *is* a realm of vagueness. It involves not only hard
fact, but intangibles like "language culture", "library availability",
"library quality", "tool availability", and "tool quality".)
>> In other words: getting rid of the log N factor in a functional
>> version of shuffling will solve the problem only very partially.
>> Unless the functional version is some simulation of array updates,
>> with a compiler that is smart enough to implement it using a
>> mutable array,
>
> Dunno what you mean by a simulation of array updates. The programmers
> model is to have an update function which returns a new array. All
> that is required (from the programmer at least) to make destructive
> updates safe is for the array to be used in the same single threaded
> manner (as far as updates are concerned) that would be used in the
> imperative version of the algorithm. This is something the compiler
> can check at compile time. Admitedly non-stricness may complicate
> matters in some languages, but not much AFAICS.
Haskell language implementors have reported the opposite.
In fact this seems to be a major stumbling block; one of those things
where the basic optimizations are easy, but as the software grows, it
gets more and more difficult to infer that some piece of data *really*
isn't used anymore.
The problem seems to be that lazy evaluation can cut across modules.
There's no easy way to tell whether the data that's submitted to a
library function will be forced. It's even worse: most likely, the data
will be partially forced, so when you construct some large object, you
don't know whether this will ever materialize. This lack of knowledge
affects both programmer and compiler: the programmer has difficulties
determining the complexity of his software (because it has become a
nonlocal property), the compiler has difficulties determining what will
be evaluated (this time because strictness is a global property).
Of course, you can still do complexity analysis in lazy languages, and
even in a modular style. Chris Okasaki's "Purely Functional Data
Structures" is a good example.
It's just that local techniques will work only as long as you have both
producer and consumer of some data structure in one module. If you don't
know who's going to read the data, you don't know how much of it is
going to be evaluated.
>> That's no FUD, that's simply the state of affairs. Functional
>> programmers do tend to use lists and trees where imperative
>> programmers use arrays. Arrays are faster unless you need
>> insertion; shuffling is an operation that doesn't need insertion;
>> so the array version is faster. Arrays are alien to most functional
>> programmers' style, so their version will be slower. I don't see
>> much debatable in such statement.
>
> What's debatable is whether this has anything to do with functional
> vs. imperative.
Agreed.
> You are essentially comparing two different algorithms, then
> (incorrectly IMO) asserting that faster one cannot be implemented
> efficiently in a FPL, and it therefore follows that FPL's are forever
> doomed to be slower than imperative languages for certain problems.
I don't see much use of arrays in textbooks on FPLs. Which leads me to
believe that arrays are atypical usage.
> So what are you saying? Sometimes you seem to be saying that the
> (purely hypothetical) slowness of FPL's is caused by a mixture of
> using traditional FP style and lack of adequate R&D effort in
> compiler technology (which may well be true), and sometimes you seem
> to be saying that slowness of FPL's for some problems is an
> unalterable law of nature, and there exists a hard proof of this.
I hope I have shed some light on my position.
Joachim Durchholz
> You can compile arrays in such a way that at an element update, the
> new copy of the array is produced by destructive update, but the old
> copy goes through a modification list. This requires an extra
> indirection for access, and an update requires creating a heap object
> and overwriting an indirection.
OK.
> The effect is that if the array is single-threaded, access and update
> are both O(1). Accesses to "old" copies can be slow as you have to
> walk through a modification list, but these can be shortcircuited (by
> making a new shallow copy of the array) in such a way that all
> accesses get O(1) randomized amortized cost. The idea is that
> whenever you walk a modification link, you make a copy with
> probability 1/N, where N is the size of the array.
Interesting approach.
I'll have to do the math myself to really understand what's going on
complexity-wise, but it seems plausible.
Here's a question to Adrian: How difficult would it be for a compiler to
recognize that it can reuse the array if user code arranged things in
this fashion? Do real compilers detect it? (It's not bad if they don't:
if this kind of code is uncommon, the optimization is usually too far
down the wishlist to get serious consideration.)
> All of the above puts some fairly hefty constant factors on running
> time, which is why it generally isn't used in compilers for FP's.
Well, it would have given an O (N) shuffling algorithm, and that's what
the challenge was about :-)
Is there some survey on the techniques that were tried and where the
overheads came from? I have some ideas about the issues, but I'd like to
check whether I'm about to reinvent the wheel :-)
Joachim Durchholz
> Søren Debois <deb...@diku.dk> writes:
>
> Nicholas Pippenger, "Pure versus Impure Lisp", in POPL'96.
Available on-line (at a cost) at:
http://portal.acm.org/citation.cfm?id=244798&jmp=review&dl=GUIDE&dl=ACM
Joachim Durchholz
> No doubt. Of course, lazy evaluation makes essential use of
> assignment (internally).
Hmm... I see a pattern here.
Okasaki uses laziness to reduce complexity in similar contexts.
Peter Van Roy
> Peter Van Roy wrote:
> > PS: I know about monads and they are not equivalent to mutable state.
> > They lack important modularity properties of mutable state.
>
> Could you be more precise?
>
> Best regards,
> Tomasz
Actually, my message is completely precise. It's just not complete :-).
I have explained this in much detail a few months ago on Lambda the
Ultimate and also on the Yahoo pragprog list. I will try to find out
where the discussions are archived. The general idea of why mutable
state gives you modularity is also explained in my book (URL
mentioned elsewhere on comp.lang.functional) but without
specifically mentioning monads.
To give the general idea, let me just mention one point. Monadic state
does threading (the state is part of the type signature of the function
both in the input and the output). Threading imposes an *order* on
execution. This order is often overkill. One simple case where monads
*cannot* replace mutable state is for programs doing declarative
concurrency, which is an interesting form of concurrency that is purely
functional (explained in chapter 4 of the above book). There is no
order defined between concurrent parts of a program. If I want to
modify a function in such a program to find out how many times it
is called or to memoize it, I cannot do so using monads. I must use
mutable state.
Peter
Peter Van Roy
Exactly. In my view, a language like OCaml is doing things right.
There's no value judgement on whether mutable state or objects
are right or wrong; rather, the language has a clean layered
structure that allows you to use state when it's needed. See
Appendix D of my book for a more detailed explanation of why
this kind of layered structure is natural:
http://www.info.ucl.ac.be/people/PVR/book.html
Peter
Jerzy Karczmarczuk
> AFAIC, using the ST monad *is* imperative programming. The monadic
> value represents the computation (which at this point is still in the
> state of not having occured). Only the manipulation of monadic values
> is pure, the execution of the computation represented by the final
> value is imperative in nature.
I don't think so.
If your state is an internal entity, a counter, or whatever, the stateful
monadic programming is as purely functional as it can.
It simply explicitizes the World.
First, monadic stage of "execution" of the program produces another program,
an awful function, where the "true computations" are finally finished, but
whose main role is to be a function composed of chunks (World -> World)
(or State if you prefer). This function applied to the initial world of
course. If there are no hidden, opaque entities, all this baroque is
as purely functional as it can be.
Jerzy Karczmarczuk
Ketil Malde
> AFAIC, using the ST monad *is* imperative programming. The monadic
> value represents the computation (which at this point is still in the
> state of not having occured). Only the manipulation of monadic values
> is pure, the execution of the computation represented by the final
> value is imperative in nature.
Shouldn't we rather talk about "pure" vs. "impure" and "imperative"
vs. "functional"? IMVHO, monadic programs are (can be?) imperative,
but also still pure.
-kzm
--
If I haven't seen further, it is by standing in the footprints of giants
Vincenzo aka Nick Name
>
> Exactly. In my view, a language like OCaml is doing things right.
Well, a lazy language just cannot do the same. I would like to hear
objections to monads, sometimes :) Why did you say that monads lacks
modularity properties? What are those properties? I know this might start a
flame war, but it's worth discussion anyway.
V.
Peter Van Roy
> > PS: I know about monads and they are not equivalent to mutable state.
> > They lack important modularity properties of mutable state.
>
> Could you be more precise?
>
> Best regards,
> Tomasz
Here is a URL to a discussion on Lambda the Ultimate on this topic:
http://lambda.weblogs.com/discuss/msgReader$9361?mode=topic&y=2003&m=11&d=1
Peter
Chris Okasaki
languages can't do a random permutation in linear time without
mutable arrays. If you're willing to accept *expected* linear
time rather than *worst-case* linear time, then here's a way
to do it that does not require mutable arrays. It uses bulk
update operations on an array, which requires O(M+N) time
to perform M updates on an array of size N.
Given a list of size K, pair every element with an random integer
in the range 1..2K. Use the "accumArray" operation in Haskell (or
something similar) to distribute the elements across an array of
size 2K. Now go through the array and collect the elements
back into a list. The only problem occurs when there is a "collision",
in which case more than one element can end up in the same
position. You can take those elements and permute them recursively,
or, if there's only a few of them, use some other ad hoc method
to permute them.
The key to this technique is that collisions will be rare, especially
collisions of more than 2 or 3 elements. The argument for this is
exactly the same argument that says that a good size for a hash table
is about twice the expected number of elements. If you want to reduce
the number of collisions even further, you can expand the array to 3K
or 4K.
-- Chris
Marcin 'Qrczak' Kowalczyk
> The argument for this is exactly the same argument that says that a good
> size for a hash table is about twice the expected number of elements.
OCaml's hash tables use the inverse ratio: they are resized when the
number of elements reaches twice the length of the array. What criterion
should I use for my own hash tables?
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Matthias Blume
I don't know why you think we disagree.
I can rewrite any imperative program as a program that is as "purely
functional as it can" be using explicit state passing or the ST monad.
But doing so has not accomplished anything -- the translation is
completely mechanical. You still look at the same program. That's
what I mean by "is imperative in nature".
The main (potential) benefit of purely functional programming is (at
least to me) that one does not have to reason about state *at all*.
When there is state, then whether or not it is being threaded through
explicitly is a secondary issue.
Explicit state passing shows that there are programs that are both
purely functional and imperative at the same time. Incidentally, the
ST monad basically makes state implicit again (or, at least, somewhat
less explicit) so that we can be sure of single-threadedness of state
(something that for performance reasons is rather desirable).
I don't see any fundamental difference between imperative programming
and programming with the ST monad. Therefore, the real point (to me)
is that the strengths of state passing and ST monad lie not so much in
how they are used but in the fact that *one does not have to use them*
when they are not needed. This contrasts with programming in
imperative languages where one cannot avoid state.
Matthias
Adrian Hey
> Interesting approach.
> I'll have to do the math myself to really understand what's going on
> complexity-wise, but it seems plausible.
I believe this is what Haskell DiffArrays do (was originally implemented
in ML by Hughes IIRC). It's constant time for updates but still carries
a fairly high constant factor overhead compared to imperative (destructive)
updates. But it should be a better option than tree based representations
in many situations.
> Here's a question to Adrian: How difficult would it be for a compiler to
> recognize that it can reuse the array if user code arranged things in
> this fashion?
If we're talking about DiffArrays the Haskell compiler doesn't do any
work. It's all library stuff. It's the programmer that decides whether
or not using a DiffArray is appropriate. In fact all array implementations
in Haskell are libraries, the language itself doesn't "know" anything
about arrays AFAIK.
> Do real compilers detect it? (It's not bad if they don't:
> if this kind of code is uncommon, the optimization is usually too far
> down the wishlist to get serious consideration.)
I don't think there's any great problem with this and a whole host of
other useful analyses, optimisations and code specialisations
(in principle:-).
I think the problem is that they are difficult to reconcile with separate
module compilation. They really require whole program analysis. Not that
this is unreasonable thing to do IMO, but then you have to start doing all
sorts or other stuff too (like sophisticated incremental re-analysis and
re-compilation schemes and such) to keep compilation times reasonable.
I hope I'm correct in saying that Clean manages to avoid this problem
(as far as uniqueness typing and the safety of destructive updates is
concerned) by requiring that the programmer decide in advance whether
or not a function accepts (and is specialised for) unique arguments.
There are other issues too, like the algorithms or heuristics used
by the compiler to determine which transformations or specialisations
actually are worthwhile optimisations (or even if they are optimisations
at all). It seems to me that careless over specialisation could result
in massive code bloat for negligible performance gain.
> Well, it would have given an O (N) shuffling algorithm, and that's what
> the challenge was about :-)
I'm 99% certain that you can do this Clean without any heavy constant
factor overhead. Unfortunately my Clean skills are a bit rusty so I won't
attempt it.
Regards
--
Adrian Hey
Adrian Hey
Also, one can't help being little suspicious about the assumptions
involved in the alleged proof, considering the abstract here..
http://www.cs.ubc.ca/cgi-bin/tr/1995/TR-95-23
contains the words..
"It is well known that cyclic list structures can be created by impure
programs, but not by pure ones."
Still I shouldn't be premature in my judgement until I've taken time
to read the paper.
Regards
--
Adrian Hey
Adrian Hey
> Erm... long-term feasibility (sp?) issues don't impress me much, sorry.
Your failure to give us a proof of your original assertion (or retract it)
doesn't impress me much either :-)
I don't think I'm being unreasonable in asking for proof in this case,
considering in the minds of many (incuding myself) the implications of your
assertion cast considerable doubt about the long term viability of FPL's and
purpose of any further FPL research. Efficiency really does matter in a
great many real world applications.
I'm not expecting the FPL compilers should be able to automagically
translate the simplest most elegant FP solution into the most tortuously
complex but efficient imperative solution (though that would be nice).
But if the only efficient solution is inherently tortuously complex,
I would expect that I should be able to implement it in an FPL as easily
as I could in an imperative language and get at least comparable (if not
superior) performance.
Regards
--
Adrian Hey
Darius
Adrian Hey <ah...@NoSpicedHam.iee.org> wrote:
> Joachim Durchholz wrote:
>
> > Interesting approach.
> > I'll have to do the math myself to really understand what's going on
> > complexity-wise, but it seems plausible.
>
> I believe this is what Haskell DiffArrays do (was originally
> implemented in ML by Hughes IIRC). It's constant time for updates but
> still carries a fairly high constant factor overhead compared to
> imperative (destructive) updates. But it should be a better option
> than tree based representations in many situations.
>
> > Here's a question to Adrian: How difficult would it be for a
> > compiler to recognize that it can reuse the array if user code
> > arranged things in this fashion?
>
> If we're talking about DiffArrays the Haskell compiler doesn't do any
> work. It's all library stuff. It's the programmer that decides whether
> or not using a DiffArray is appropriate. In fact all array
> implementations in Haskell are libraries, the language itself doesn't
> "know" anything about arrays AFAIK.
How would you propose to implement arrays with the same time and space
complexity in terms of anything else provided by Haskell 98? (Actually,
now they could be implemented via the tools in the FFI libraries, but
that amounts to the same thing as having a built-in Array type.)
Ben Rudiak-Gould
<ah...@NoSpicedHam.iee.org> wrote:
>Also, one can't help being little suspicious about the assumptions
>involved in the alleged proof, considering the abstract here..
>
> http://www.cs.ubc.ca/cgi-bin/tr/1995/TR-95-23
(Note to readers: the paper can be downloaded for free from this URL.
A previously posted URL required payment.)
>contains the words..
>
> "It is well known that cyclic list structures can be created by impure
> programs, but not by pure ones."
Yes, I found that peculiar too. What he means is that it can't be done
in Lisp if you remove RPLACD from the language, but it does suggest
that he isn't very familiar with the world of pure languages outside
of Lisp.
>Still I shouldn't be premature in my judgement until I've taken time
>to read the paper.
Both papers are interesting in theory, but not in practice. In real
life, eager-evaluated languages have mutable state (except for
Unlambda...), and lazy-evaluated languages have linear-update
mutability (except for ???). There do exist constant-factor embeddings
of either of these in the other, so we can all rest easy.
And anyway, as I keep saying, factors of log n are meaningless.
-- Ben
Jerzy Karczmarczuk
>>
>>
>>>... the execution of the computation represented by the final
>>>value is imperative in nature.
>>
>>I don't think so.
>>monadic programming is as purely functional as it can.
>>
>>It simply explicitizes the World.
>>as purely functional as it can be.
>
>
> I don't know why you think we disagree.
>
> I can rewrite any imperative program as a program that is as "purely
> functional as it can" be using explicit state passing or the ST monad.
> But doing so has not accomplished anything -- the translation is
> completely mechanical. You still look at the same program. That's
> what I mean by "is imperative in nature".
> Explicit state passing shows that there are programs that are both
> purely functional and imperative at the same time.
> I don't see any fundamental difference between imperative programming
> and programming with the ST monad. ...
> ... This contrasts with programming in imperative languages where one
> cannot avoid state.
Aaaaa!
The issue was my understanding of your words "imperative by nature".
Two last quotes above (sorry for the massacre of your text) suggest that
you want to underline *at the same time* the differences between languages
and the equivalence of their paradigms at the abstract level. I might
quote Enya now: "May it be"...
For me the difference is elsewhere, though.
The imperative *programs* in ANY language cannot avoid state. Whether it
is (low-level) monadised, or using unique-access variables as in Clean,
or in classical imperative languages - doesn't matter. What matters in the
"real" existence of the external state entity, the World. For me *this*
is "imperative by nature".
On the other hand, when you are allowed to reason without this state, then
even in Visual Cobol you can write genuinely functional programs. And the
high-level monadic stateful computations in Haskell are functional in nature,
without any necessity to pronounce "imp..." or other Forbidden Spells.
But, you are right, no reason to dispute, all this is a bit of philosophical
hairspliting...
Jerzy Karczmarczuk
Joachim Durchholz
> The general idea of why mutable state gives you modularity is also
> explained in my book (URL mentioned elsewhere on
> comp.lang.functional) but without specifically mentioning monads.
Hmm... I think that monads are just one way of achieving a certain kind
of modularity, while mutable state is another one.
From my perspective, mutable state can decouple modules (i.e. decrease
inter-module dependencies) by making a communcation channel implicit. Of
course, implicit channels are usually a bad idea, but they are OK
modularity-wise if the module talks to nobody but itself (and maybe a
small, fixed, documented set of other modules).
> This order is often overkill. One simple case where monads *cannot*
> replace mutable state is for programs doing declarative concurrency,
> which is an interesting form of concurrency that is purely functional
> (explained in chapter 4 of the above book).
I have yet to see how declarative concurrency is different from
by-default lazy evaluation. Could you elaborate?
> If I want to modify a [monadic] function to find out how many times
> it is called or to memoize it, I cannot do so using monads. I must
> use mutable state.
AFAIK this can be addressed by monad transformers. (Integrating a new
monad transformer into a set of given transformers requires some work,
but it's a one-time investment.)
Joachim Durchholz
> [OCaml] has a clean layered structure that allows you to use state
> when it's needed. See Appendix D of my book for a more detailed
> explanation of why this kind of layered structure is natural:
> http://www.info.ucl.ac.be/people/PVR/book.html
I think both the book and OCaml get one important detail wrong: the
signature of a function gives no warning if it has side effects. In
other words, I have to look at the implementations of all functions just
to check what logic I can use to reason about a program...
I think an approach like uniqueness typing would be called for: an
annotation on a name's definition that tells me whether that name is
mutable or not. (If the name is declared as a mutable record, it might
help if the record elements themselves are declared mutable or not.)
<think-as-you-write mode>
Add rules for mutability inference. Say, a function is inferred to be
"mutable" (well, the terminology clearly leaves room for improvement) if
it uses a mutable name, except if either the programmer declares that
that mutable name's statefulness cannot affect callers, or if the
compiler can infer the fact (the latter would be an, erm, interesting
research project, I think *g*).
</think-as-you-write mode>
Joachim Durchholz
> OCaml's hash tables use the inverse ratio: they are resized when the
> number of elements reaches twice the length of the array. What criterion
> should I use for my own hash tables?
Whatever you like if only the increase is exponential (i.e. you increase
by a constant factor at a given fill ratio).
I think the best ratios and factors can only be determined by
experimenting. I find it a bit strange that OCaml deliberately generates
overflows in its hash tables; I'd look for an explicit comment in such
code that states that this 200% ratio is intentional and gives an
argument why it is so, I'd suspect a bug and reverse the ratio to 50%.
Typical hash table figures are a fill ratio between 70% and 85%, and a
growth factor between 1.141 and 2. Usually there's also a routine to
explicitly increase the size to a given value (for situations where the
client knows in advance how large the table will be), to tweak ratio and
factor (when the programmer did his own profiling and found that, for
his usage, the table would work better with different parameters), and
to switch off automatic growth entirely (when the client uses the hash
table for a known set of keys, e.g. programming language keywords, and
wishes to fill the hash table to exactly 100% without triggering a resize).
HTH.
Lauri Alanko
> <think-as-you-write mode>
> Add rules for mutability inference. Say, a function is inferred to be
> "mutable" (well, the terminology clearly leaves room for improvement) if
> it uses a mutable name, except if either the programmer declares that
> that mutable name's statefulness cannot affect callers, or if the
> compiler can infer the fact (the latter would be an, erm, interesting
> research project, I think *g*).
> </think-as-you-write mode>
Some magical words that may interest you are "type and effect system",
"region inference" and "effect masking".
Lauri Alanko
l...@iki.fi
Torben Ægidius Mogensen
You can do this with a type-and-effect system, similar to the one used
by region inference. But you would use sets of read and assigned
variables instead of regions for the effects. IF a variable is not in
scope and is not free in the type, you can remove it from the effect
list, thus encapsulating the side-effect. In this way, a function
that has a pure (effect-free) type can use side-effects locally. I/O
can be seen as access to a global mutable variable.
The rule for removing variables from the effect list is exactly the
same as the let-region rule in region inference, but you probably
don't need the equivalence of region polymorphism, so the rules should
be simpler.
You can also add raised exceptions as effects, removing them when they
are handled.
I would like to see a language that is like ML, but:
1) Has effect-types like described above.
2) Makes boxing explicit, i.e., the default is no boxing.
3) Allows nullable pointer (box) types (using different types than
not-nullable pointers).
4) Has Haskell-like type classes.
5) Allows allocation of boxed values on the stack. The compiler
should check for escapes.
6) Avoids context-dependent syntax (like the need in SML to know if a
name is a constructor or a variable to parse a pattern). This is
bad for programmer and compiler-writer alike.
I have toyed with the idea of making such a language myself, but have
only a very rudimentary set of notes (with wish lists and ideas for
implementation).
Torben
Joachim Durchholz
> Joachim Durchholz wrote:
>
>> Erm... long-term feasibility (sp?) issues don't impress me much,
>> sorry.
>
> Your failure to give us a proof of your original assertion (or
> retract it) doesn't impress me much either :-)
Not sure which assertion you mean. (See below)
> I don't think I'm being unreasonable in asking for proof in this
> case,
Yes, efficiency does matter.
If you mean the typical O (log N) slowdown assotiated with list
algorithms when compared to array algorithms: it's both questionable (as
some have pointed out) and irrelevant (as I have pointed out), so I
don't think there's much of a point.
If you mean the statement that FPLs tend to be slower by a constant
factor, then I agree here's grounds for debate.
> considering in the minds of many (incuding myself) the implications
> of your assertion cast considerable doubt about the long term
> viability of FPL's and purpose of any further FPL research.
> Efficiency really does matter in a great many real world
> applications.
It doesn't cast any doubts in my mind. Large projects still keep
failing. One of the reasons is fuzzy customer requirements, which means
lots of software rewrites to accommodate the specification-of-the-day -
FPLs should excel here.
Another reason is that large projects tend to produce bloated, slow
code. One of the reasons why large software is slow is excessive data
copying, a point at which FPLs are already known to excel. (If there's
little data copying, the software tends to have many sharing-related
bugs, which is even worse than being slow.)
Efficiency issues are a serious entry barrier, but they are not a
serious problem in the long term. Look at Java - its standard
implementation has an efficiency that does injustice to the word, yet
it's getting more and more standard. While Java has had some very
negative effects, it has lowered the standards for efficiency in a way
that's unbelievable. Claiming a better speed than Java while retaining
its advantages could be a real scoop :-) (iff the claims sound plausible
- and one of the things that make Java attractive is the long-term
commitment by a large company; that's difficult to match by an FPL until
it gets public commercial commitment).
In other words, I don't think there's real reason to nurture this kind
of doubt.
> I'm not expecting the FPL compilers should be able to automagically
> translate the simplest most elegant FP solution into the most
> tortuously complex but efficient imperative solution (though that
> would be nice). But if the only efficient solution is inherently
> tortuously complex, I would expect that I should be able to implement
> it in an FPL as easily as I could in an imperative language and get
> at least comparable (if not superior) performance.
Tortuously complex algorithms are the exception. Most algorithms are
dead simple (to the point of not being recognized as "algorithms" but
just simple "code" - think mapping database values to an internal form,
validity checks, and similar stuff).
I agree that complex algorithms are easier to do in functional
languages, and I wouldn't be surprised if the functional implementation
is on par with its imperative counterpart. However, it's the simple
things where imperative languages make it easy to write a fast solution,
while it's not so easy in an imperative one. I think the best way to
phrase it is to say: "You get a certain amount of efficiency 'for free'
in an imperative language, just as you get a certain amount of
modularity 'for free' in functional languages".
Given the current sizes of software, I know what kind of language I'd
want to side with :-)
Chris Okasaki
> Chris Okasaki wrote:
> > The argument for this is exactly the same argument that says that a good
> > size for a hash table is about twice the expected number of elements.
>
> OCaml's hash tables use the inverse ratio: they are resized when the
> number of elements reaches twice the length of the array. What criterion
> should I use for my own hash tables?
If you're using open addressing, then you probably want to resize when you
hit a load factor (num elements/size of array) of around 0.75. If you're
using separate chaining, then it doesn't matter nearly as much. Resizing
when you hit a load factor of anywhere from 0.75 to 2 is perfectly
reasonable.
BTW, anybody up for some benchmarks for this linear scheme versus one of
the tree based approaches?
-- Chris
Marshall Spight
> To avoid being FUDdy one
> should also add that even the least optimizing FPL compilers will beat
> JVM and .net interpreted code, hands down, every time :-)
That's a pretty strong statement. Do you have any citations for it?
When you say "interpreted code" are you referring to any code
run in the JVM, or do you mean just "-Xint" (formerly "--nojit"?)
Certainly if you turn the jit/hotspot compiler off, what you say
is true.
Marshall
Torben Ægidius Mogensen
> "Joachim Durchholz" <joachim....@web.de> wrote in message news:bueve0$38b$1...@news.oberberg.net...
> > To avoid being FUDdy one
> > should also add that even the least optimizing FPL compilers will beat
> > JVM and .net interpreted code, hands down, every time :-)
>
> That's a pretty strong statement. Do you have any citations for it?
I have some anecdotal evidence, at least. The Moscow ML compiler is a
non-optimizing ML compiler that compiles to interpreted bytecode
(using the CAML-Light VM). Recently a backend targeting the .NET
platform has been added. In spite of the .NET bytecode being JIT
compiled, the .NET version still runs 2-4 times slower than the
original Moscow ML. More if exceptions are used extensively.
What would be more interesting is comparing SML.NET to Moscow ML.
SML.NET is a very advanced ML compiler using whole-program analysis
and a host of general and .NET-specific optimizations. If SML.NET is
not able to run appreciably faster than Moscow ML (using the
CAML-Light VM), we can conclude that the .NET platform is ill suited
for functional languages.
Torben
Joachim Durchholz
> "Joachim Durchholz" <joachim....@web.de> wrote:
>
>> To avoid being FUDdy one should also add that even the least
>> optimizing FPL compilers will beat JVM and .net interpreted code,
>> hands down, every time :-)
>
> That's a pretty strong statement. Do you have any citations for it?
Some personal experience and lots of reports on the net wrt. Java.
A good summary and a few references (that I haven't checked) can be
found on http://www.bearcave.com/software/java/why_native.html .
I don't have the same kind of evidence for .net; my assessment is more a
personal belief, partly stemming from the fact that whenever I see a
statement from Microsoft, I assume the opposite by default :-)
However, I think that a system-wide infrastructure needs lots of
facilities that make global optimization difficult, particularly
introspection and dynamic code loading.
In know that introspection need not slow a system down, but you have to
design for that - and I simply don't expect Microsoft to be able to do
that, their development processes are too market-driven to allow their
designers enough time to get it right.
Getting dynamic code loading right so that it doesn't burden a system is
even more of a challenge; I have been tinkering with some designs that
try to achieve this, and it turned out that it's practically impossible
to get this up to speed unless you add some pretty pervasive
infrastructure. (I think it *can* be done, it's just nothing that you
can add as an afterthought, and since it's pervasive I expect that this
will cut down the design space by a considerable amount.)
Also note that I specifically wrote "interpreted" .net - that's not its
normal mode of operation. .net is centered around the
compile-as-you-install approach (in contrast with HotSpot's
compile-as-you-run approach). It will be interesting to see how fast (or
slow) the dotnetted versions of Windows will be. (Unfortunately, the
numbers will be difficult to compare since MS will be packing all sorts
of luggage into Windows.)
Oh, and despite many claims and arguments to the contrary, interpreted
code is really slower than machine code :-)
Of course, things have progressed. Initially, interpreters were so slow
that they were used for nothing but toys (and Lisp, which took decades
to break out of its AI niche). Today, the slowdown that's incurred by
using an interpreter is somewhere between a factor of 2 and 10. That's
not too bad, especially since many systems are bound by IO or user
response time, not CPU.
Also, the general trend towards using C as an intermediate language
seems to be resulting in disappointing performance. I don't know the
exact reasons, but if this observation is more than anecdotal, then it's
indeed possible that VMs can be as fast as compiled code...
Adrian Hey
> Adrian Hey wrote:
>> Your failure to give us a proof of your original assertion (or
>> retract it) doesn't impress me much either :-)
>
> Not sure which assertion you mean. (See below)
Take your pick..
"There's no way that any functional variant of shuffling is as
fast as the mutable array version, even if it's O (1)."
"Purely functional languages cannot express everything in the same
complexity as imperative languages."
> If you mean the typical O (log N) slowdown assotiated with list
> algorithms when compared to array algorithms: it's both questionable (as
> some have pointed out)
Errm.. It certainly is questionable. I won't ask you to retract that too
'cos I guess what you wrote isn't what you really meant :-)
But with regard to relevance of an O(log N) difference (if one exists)
you and others can say what you like about this being irrelvant,
a chimera, or whatever. I just don't buy that, and I don't think many
other sane array users will either. For arrays the performance differences
between the various approaches that have been discussed are *huge*.
If, as you assert, FPL's can't provide arrays with the same performance
as an imperative language (even in principle) that will be percieved as
a show stopping issue by many potential users, correctly IMO. Fortunately
things ain't that bad even in reality (if one looks at Clean).
But dog slow can be cool too, I guess.. well sometimes.. :-)
Regards
--
Adrian Hey
Adrian Hey
> How would you propose to implement arrays with the same time and space
> complexity in terms of anything else provided by Haskell 98?
That's a strange question. Why would I propose to do that? It's not
possible AFAICS.
To get optimised array processing code out of a compiler don't you need
to somehow write array semantics and syntax into the definition of the
language in the first place? That hasn't been done with Haskell so
Haskellers will always be stuck with library array implementations
(well at least until the definition of Haskell is revised).
Regards
--
Adrian Hey
Joachim Durchholz
> Joachim Durchholz wrote:
>
> But with regard to relevance of an O(log N) difference (if one
> exists) you and others can say what you like about this being
> irrelvant, a chimera, or whatever. I just don't buy that, and I don't
> think many other sane array users will either. For arrays the
> performance differences between the various approaches that have been
> discussed are *huge*.
Well, my stance is not that the difference between array and list
implementations is irrelevant.
What I'm saying is that, other factors being equivalent, the different
between O (N) and O (N log N) is irrelevant. IOW if I have an array
algorithm, and extend it slightly (say, by collecting some statistics or
whatever), and this change will bump the algorithm up from O (N) to
O (N log N), I'll probably not care very much. Constant-factor
differences are far more relevant than that O (log N) difference.
I agree that going from an array to a list representation incurs quite
large constant factors (this seems to be a case of violent agreement *g*).
> If, as you assert, FPL's can't provide arrays with the same
> performance as an imperative language (even in principle) that will
> be percieved as a show stopping issue by many potential users,
> correctly IMO.
With the new information from this thread, I'd say the situation is a
bit more complicated (as things tend to be when it comes to performance).
People who just read the textbooks and didn't explore the libraries too
deeply will probably recode everything using lists, with a severe
performance hit. As said above, there's often a negligible O (log N)
factor involved, and a not-so-negligible constant factor for allocating
and freeing lots of small memory blocks. (Which leads me to the question
whether garbage collecting N list nodes is an O (N) or O (N log N)
activity... things are getting *really* muddy at this point.)
Additionally, an array implementation more-or-less guarantees data
access locality while list implementations don't (but usually will have
some locality attributes as well, and these effects serve to further
muddy the waters...)
For people who have immutable array types at their disposal, things will
probably be much faster. As far as I can tell, you end up with quite
small (if any) constant overhead, though this tends to incur an
O (log N) overhead if immutability is involved.
Finally, one can use full mutable arrays, even in an FPL. That's
something that's often forgotten, since immutability is one of those
dogmas that tend to override reality (and I admit being guilty of that,
too - my excuse is that the original poster probably would consider that
cheating *g*). In that case, there's no real overhead in an FPL.
Personally, I could live well without mutable arrays. In a language
without uniqueness annotations, they must stay strictly local; in a
language with uniqueness annotations, programmers have to tinker with
the code to make sure that the array is copied whenever it's necessary.
In other words, the sharing problems with mutable state are not solved,
they are just made explicit (which is far better than the usual approach
of leaving the problem to the debugging phase).
But that's just my personal taste. Mutable state as such is unavoidable
anyway, and it may well be that uniqueness annotations are the best
compromise.
Ralph Becket
> Darius wrote:
>
> To get optimised array processing code out of a compiler don't you need
> to somehow write array semantics and syntax into the definition of the
> language in the first place? That hasn't been done with Haskell so
> Haskellers will always be stuck with library array implementations
> (well at least until the definition of Haskell is revised).
While the O(1) properties of arrays depend upon destructive update, you
don't have to specifically build array semantics into a (pragmatically)
pure language: you only need some mechanism allowing controlled impurity.
This is absolutely necessary for IO at the very least: you don't
find IO semantics built into pure declarative languages, IO semantics are
just a property of the libraries that you use to do IO (and arrays and
hash tables and...)
Various mechanisms can be employed to get what you want. Haskell uses
monads, Mercury and Clean use uniqueness, and anybody who can wrap up
some impure code behind a pure interface in their language can provide
version arrays.
-- Ralph
Adrian Hey
> Adrian Hey <ah...@NoSpicedHam.iee.org> wrote in message
>> To get optimised array processing code out of a compiler don't you need
>> to somehow write array semantics and syntax into the definition of the
>> language in the first place? That hasn't been done with Haskell so
>> Haskellers will always be stuck with library array implementations
>> (well at least until the definition of Haskell is revised).
>
> While the O(1) properties of arrays depend upon destructive update, you
> don't have to specifically build array semantics into a (pragmatically)
> pure language:
Realistically I think you do (if you ever hope to even come close to the
performance a C or Fortran programmer can achieve). The fact that
complexity may be O(1) is *by no means* enough. (Have you tried using
ghc's DiffArrays recently :-)
Perhaps the performance of STArrays may not be quite so appalling
(I haven't had time rewrite the relevant code yet), but even here
I will likely incurr (at a minimum) the cost of a function call
for every read/write (as seems inevitable with any function provided
in a library). This alone will be real performance killer in for
many applications.
And so far in this thread we've only really being talking about doing
"itsy bitsy" random read/writes of single array elements. This style
of array access may be necessary sometimes, but more often I think folk
will be writing code to crunch entire arrays in some regular and
systematic manner. If the language provides some means for programmers
to tell the compiler what thay are actually trying to do, it stands
a much better chance of generating decent code by allowing all sorts
of sophisticated transformations, array fusion optimisations, and
blisteringly fast iteration and/or parallelisation.
Regards
--
Adrian Hey
Marcin 'Qrczak' Kowalczyk
> even here I will likely incurr (at a minimum) the cost of a function
> call for every read/write (as seems inevitable with any function
> provided in a library).
It does not. GHC inlines functions across modules.
Adrian Hey
> On Fri, 23 Jan 2004 15:27:50 +0000, Adrian Hey wrote:
>
>> even here I will likely incurr (at a minimum) the cost of a function
>> call for every read/write (as seems inevitable with any function
>> provided in a library).
>
> It does not. GHC inlines functions across modules.
Oh, sorry. Well I did say "likely" :-) But maybe this doesn't happen
in the particular case of STArrays and ghc. But it can presumably only
do this if array implementation is Haskell (and that implementation itself
makes no function calls of course), not all library array implementations
in general.
IOW I'd still have this as a limiting performance factor even if tried to
implement my own DiffArrays in hand made assembler. (Something I'd been
considering, but it's difficult to see how I could ever hope to do this
(relatively:-) efficiently without some scarey low level access to the
Haskell heap and rts).
Anyway, this is all fairly academic without knowing the efficiency
of what's being inlined, considering for things like unboxed floats
most processors can do an array write (and some pointer arithmetic
if necessary) in a single instruction. On the DSP's I use I can do a
lot more than that in a single instruction.
Regards
--
Adrian Hey
Peter Van Roy
>
> I have yet to see how declarative concurrency is different from
> by-default lazy evaluation. Could you elaborate?
Lazy evaluation is *completely different* from declarative
concurrency. They're orthogonal in a language. All I can
say is, read chapter 4 of my book:
http://www.info.ucl.ac.be/people/PVR/book.html
Peter
Peter Van Roy
> Peter Van Roy wrote:
>
> > [OCaml] has a clean layered structure that allows you to use state
> > when it's needed. See Appendix D of my book for a more detailed
> > explanation of why this kind of layered structure is natural:
> > http://www.info.ucl.ac.be/people/PVR/book.html
>
> I think both the book and OCaml get one important detail wrong: the
> signature of a function gives no warning if it has side effects. In
> other words, I have to look at the implementations of all functions just
> to check what logic I can use to reason about a program...
This is an amazingly persistent dogma. I had a long discussion about
it on the Yahoo pragprog list a few months ago. It's completely wrong
for a language to *force you* to say in a function signature whether
the function internally uses state or not. There are many cases when
you don't want to say it (and other cases when you *do* want to say
it, of course). It's the responsibility of the function's implementor
whether or not the function *behaves* as a pure function. If he/she
says it is so, then you *can* reason about the function as a pure
function, no matter how it is implemented. If the type system can
*prove* it is pure, so much the better. But even if it can't, the ability
to declare the function as pure is an essential one that shouldn't be
sacrificed on the altar of a weak type system.
The book considers this so important that it elevates it to a principle:
the "Model Independence Principle". That is, the externally visible
interface of a module should not depend on the computation model
used to implement the module.
I have thought a lot about the issues and I am personally convinced
that this principle is correct.
Peter
Joachim Durchholz
>> by-default lazy evaluation. Could you elaborate?
>
> Lazy evaluation is *completely different* from declarative
> concurrency. They're orthogonal in a language. All I can say is,
> read chapter 4 of my book:
Been there, done that (didn't get the T-shirt though *g*).
The mechanisms are very different, yes.
Umm... maybe I should have said: Lazy evaluation and declarative
concurrency *as by-default evaluation mechanisms*.
In lazy evaluation, a function call is expanded into the function's
declaration on a by-need basis.
In declarative concurrency, bindings of values to names are executed on
an on-availability basis. (I hope I did get that right.)
I suspect the set of orders in which primitive functions might be called
is the same, regardless of which of the two evaluation strategies you
use.
My current thinking is that the two are different ways to express the
same thing.
(To the very least, they try to achieve the same thing: minimize
ordering constraints on elementary computations.)
Hope I clarified myself a bit.
Joachim Durchholz
> Joachim Durchholz <joachim....@web.de> wrote:
>
>>I think both the book and OCaml get one important detail wrong: the
>>signature of a function gives no warning if it has side effects. In
>>other words, I have to look at the implementations of all functions just
>>to check what logic I can use to reason about a program...
>
> This is an amazingly persistent dogma. I had a long discussion about
> it on the Yahoo pragprog list a few months ago. It's completely wrong
> for a language to *force you* to say in a function signature whether
> the function internally uses state or not.
I agree this shouldn't be part of a function's signature - if the most
efficient implementation of some algorithm involves state, who cares as
long as this statefulness doesn't leak to the caller?
However, I talked about side effects. These are observable from the outside.
This has all sorts of ramifications: it heavily impacts the semantic
phases of compilers (if the compiler has reliable information on side
effects, some program transformations can be done in an entirely more
liberal fashion), and there's a profound (though indirect) influence on
program maintenance.
So, yes, I think that programmers should be encouraged to state whether
a function has side effects.
Since programmers usually don't get the time to do things right, the
ideal system would force programmers to annotate a function if it uses
side effects. If a function uses state but is supposed to have no side
effects, there should be a proof that no such side effects indeed exist.
I don't care whether that proof is provided by the compiler or the
programmer, in practice this will be probably a mixture of a few
annotations by the programmer and automated inference, unless the
programmer wants to do something fancy like hiding a large stateful
algorithm under a narrow stateless interface.
> There are many cases when
> you don't want to say it (and other cases when you *do* want to say
> it, of course).
Exactly.
> It's the responsibility of the function's implementor
> whether or not the function *behaves* as a pure function. If he/she
> says it is so, then you *can* reason about the function as a pure
> function, no matter how it is implemented. If the type system can
> *prove* it is pure, so much the better. But even if it can't, the ability
> to declare the function as pure is an essential one that shouldn't be
> sacrificed on the altar of a weak type system.
I don't share your trust in the ability of programmers to decide whether
a function is pure or not.
Beside, pureness should be a more fine-grained property. For example,
the transcendental functions in the usual C libraries are impure in that
they set a global error flag, yet they are pure if you consider just
their results. (I don't have any good ideas how this should be handled
in practice, but I think that's a real issue.)
Peter Van Roy
> My current thinking is that the two are different ways to express the
> same thing.
I'm sorry, but this is completely wrong.
Lazy evaluation is *coroutining* and hence sequential.
Lazy evaluation does the minimal number of reductions.
Declarative concurrency is really concurrent: different parts
of the computation can be unordered.
Declarative concurrency gives *slack*: a producer can
be programmed to run ahead of a consumer. This does
not necessarily use the minimal number of reductions.
How about going back and reading the chapter again!
Peter
Joachim Durchholz
> How about going back and reading the chapter again!
Sorry, but I don't feel like doing that.
It would help me more if you gave a hint where exactly you disagree,
having to reread entire chapters just to clear up a misunderstanding
would save me *lots* of my time, with no guarantee that I understand
your position, while it would cost you comparatively little time (and
also help those onlookers who don't have the time, network bandwidth, or
printing resources to download, print and read the book).
> Joachim Durchholz <joachim....@web.de> wrote:
>
>> My current thinking is that [declarative concurrency and laziness]
>> are different ways to express the same thing.
>
> I'm sorry, but this is completely wrong.
Oops... you're right. Sorry for typing faster than thinking - I got the
concepts totally mixed up. (There *is* a parallel between concurrency
and lazy evaluation, but it's entirely unapplicable and not very
relevant in general - but noticing that parallel sent my intuition on a
journey into a long blind alley.)
Let me go back to the original issue:
You stated that monads cannot replace declarative concurrency.
My first reaction was "but I can do it with monads as well".
Initially, this ended up with "I can simulate that with a State monad".
I considered that cheating.
However, here's a way that doesn't cheat - or just minimally so :-)
To construct that hypothetical Concurrency monad, I observe that both
monads and concurrent computations are containers for computations
(well, anything that produces an output from an input; closures will do
just fine as a very general model).
Further, the monad laws are pretty liberal. They require that you can
join monads to form a greater monad, and that this join operation is
associative, and that's about all (the remaining laws deal with ways to
lift a computation into a single-element monad and similar interface stuff).
Declaratively-concurrent computations satisfy that quite well. Joining
pools of declaratively-concurrent computations is an associative
operation (and, moreover, a commutative one - that's something that the
monad laws don't require, but they don't prohibit it either).
The snag is that since this pools of DC computations is unordered, there
must be a way to link up operations. In languages with explicit
concurrency built right in, this is done by the compiler; for other
languages, you either need some minimal introspection facilities (to
determine the names of the results, and to link up the result names with
the unbound variables in the other computations), or the computations
have to be built with explict linkage right from the start (in which
time you don't really need the monad anyway).
It's still cheating, but it does show a strong structural similarity
between monads and declarative concurrency, IMVHO.
Tomasz Zielonka
> Tomasz Zielonka <t.zie...@zodiac.mimuw.edu.pl> wrote in message news:<slrnc0lurl.2...@zodiac.mimuw.edu.pl>...
>> Peter Van Roy wrote:
>> > PS: I know about monads and they are not equivalent to mutable state.
>> > They lack important modularity properties of mutable state.
>>
>> Could you be more precise?
>>
>> Best regards,
>> Tomasz
>
> Here is a URL to a discussion on Lambda the Ultimate on this topic:
> http://lambda.weblogs.com/discuss/msgReader$9361?mode=topic&y=2003&m=11&d=1
I see what you mean. Yes, this can be a problem. On the other hand
unrestricted mutable state can lead to problems. I am not sure which
is better/worse. I think I had much more problems with unrestricted
mutable state than with modularity issues of monadic state, but YMMV.
Some of problems with mutable state could be fixed by a more rigid
language definitions. For example, in OCaml the order of evaluating
function parameters is unspecified. In practice it seems to be right to
left, so when you are using side effects when eg. creating a tuple, the
results can be unexpected:
# let r = ref 0 ;;
# let next () = r := r! + 1; !r ;;
# (next (), next ()) ;;
- : int * int = (2, 1)
#
BTW. The same goes for C and C++. I is so boring to read again and again
those "clever" C/C++ programming questions, like:
What will it print
int i = 0;
printf("%d %d\n", ++i, ++i);
[Then author of the question claims that it should be 1 2 or 2 1,
because gcc or vc++ does it this way]
This is a micro-scale issue, but there are also large scale problems.
This implicit communication channels you are advertising can obscure the
code and increase it's complexity. But yes, I agree that they can be
very useful when used cleverly. I even use these techniques in Haskell.
Unfortunately I too often see code in which unnecessary mutable state
causes problems, and there are languages where it is so difficult to
avoid using mutable state.
PS. Yes, I know I haven't said anything new.
> Peter
Best regards,
Tom
--
.signature: Too many levels of symbolic links
Adrian Hey
> Peter Van Roy wrote:
>> Tomasz Zielonka <t.zie...@zodiac.mimuw.edu.pl> wrote in message
>> news:<slrnc0lurl.2...@zodiac.mimuw.edu.pl>...
>>> Peter Van Roy wrote:
>>> > PS: I know about monads and they are not equivalent to mutable state.
>>> > They lack important modularity properties of mutable state.
>>>
>>> Could you be more precise?
>>>
>>> Best regards,
>>> Tomasz
>>
>> Here is a URL to a discussion on Lambda the Ultimate on this topic:
>>
http://lambda.weblogs.com/discuss/msgReader$9361?mode=topic&y=2003&m=11&d=1
>
> I see what you mean.
I don't see the problem at all.
Peter's post at the above link was about counting the number of times some
unspecified thing (but I assume a "function" is implied) in Module E
*performs* some operation.
Maybe I've completely lost the plot wrt semantics of FPL's, but I could've
sworn that functions never *perform* anything. They don't even perform
computation, nor do they "call" other functions.
In Haskell, the only things that can perform something are *actions* in
the IO monad (when invoked). It doesn't make any sense to instrument
a function to see how many times it performs anything.
What can that possibly mean?
So, assuming the unspecified thing in E that needs instrumenting is indeed
an action in the IO monad, what's the problem with using a top level IORef?
How does Haskell differ in this respect from the imperative languages Peter
seems (albeit implicitly) to be talking about? These also can't instrument
functions, only in this case it's because there aren't any functions to
instrument :-)
[A bit of unsafePerformIO hackery needed is at the moment to create IORefs
at the top level (because Haskell currently lacks "official" syntax to
augment the world with top level mutable state), but it's a perfectly
reasonable thing to do I think.]
Regards
--
Adrian Hey
Joachim Durchholz
>
> Maybe I've completely lost the plot wrt semantics of FPL's, but I
> could've sworn that functions never *perform* anything. They don't
> even perform computation, nor do they "call" other functions.
The issue not related to semantics of FPLs. Sometimes one wants to know
more than the result of an expression, for diagnostic purposes - for
example, the actual execution path taken. Or ratios between the
alternatives of a conditional expression.
> In Haskell, the only things that can perform something are *actions*
> in the IO monad (when invoked). It doesn't make any sense to
> instrument a function to see how many times it performs anything.
It does make sense.
It's just not expressible within Haskell's graph reduction semantics.
It's a property of the concrete language implementation that's being
measured here, not a property of the program under the semantics of the
language.
One could actually express things like "number of reductions called"
within Haskell, by using a Haskell interpreter written in Haskell, but
then you measure properties of that interpreter, so it's not an option.
Regards,
Jo
Adrian Hey
> It does make sense.
> It's just not expressible within Haskell's graph reduction semantics.
[Actually I don't think Haskell does have graph reduction semantics.
I think Clean does, and maybe Haskell should have too. But at the moment
graph reduction is just an implementation technique for Haskell AFAIK.]
But I agree with your basic point, though I would say it's not meaningful
in Haskell's declarative semantics (but it is expressible in Haskell using
unsafePerformIO hackery).
> It's a property of the concrete language implementation that's being
> measured here, not a property of the program under the semantics of the
> language.
Yes indeed. I think this is the key point when considering questions
like this. Are all Haskell implementations required to yield the same
instrumentation results for the same program (if the language allowed
such things)?
If so then we're effectively turning Haskell into an imperative language.
If not we have ambiguous programs. Now ambiguity may be OK, to find out
something about the underlying implementation or what transformations and
optimisations have been implemented (such as the diagnostic examples you
gave), but somehow I don't think this is what Peter had in mind.
The "unsafe" in "unsafePerformIO" is there for a very good reason. It really
is *unsafe*, in the sense that it's effect on a program is ambiguous.
(There are circumstances where it can be made unambiguous for practical
purposes, but Peter's instrumentation example isn't one of them.)
Regards
--
Adrian Hey
Andreas Rossberg
>
> The "unsafe" in "unsafePerformIO" is there for a very good reason. It really
> is *unsafe*, in the sense that it's effect on a program is ambiguous.
It *really* is unsafe because it is unsound.
- Andreas
Adrian Hey
Isn't that what I said?
That's just different words for what I've been trying to say anyway.
Regards
--
Adrian Hey
Andreas Rossberg
>>
>>>The "unsafe" in "unsafePerformIO" is there for a very good reason. It
>>>really is *unsafe*, in the sense that it's effect on a program is
>>>ambiguous.
>>
>>It *really* is unsafe because it is unsound.
>
> Isn't that what I said?
> That's just different words for what I've been trying to say anyway.
Well, ambiguity is bad. But in fact, a program using unsafePerformIO can
even crash Haskell. I'm not sure you meant that.
- Andreas
Steve Harris
> > > PS: I know about monads and they are not equivalent to mutable state.
> > > They lack important modularity properties of mutable state.
> Here is a URL to a discussion on Lambda the Ultimate on this topic:
> http://lambda.weblogs.com/discuss/msgReader$9361?mode=topic&y=2003&m=11&d=1
> Peter
Thanks for the link to that discussion. It sortof left me hanging
though, I thought the best objection to your argument was unanswered
at the end (I don't know enough about monads to be sure though). I'll
reproduce it here (by Kirsten Chevalier) in case you or anybody else
wants to make any comments on it (hope Kirsten doesn't mind me
reposting his objection).
>> (Peter Van Roy:)
>> Now let's say I want to instrument E, to count how many times
>> it is performing some operation, and I want to observe this
>> from A. If I want to program this in a purely functional
>> way (e.g., in the pure subset of Haskell), then I am obliged
>> to change the interfaces of all the modules A, B, C, D, and
>> E (*). If I have true state, then I can get by with changes
>> in just A and E. In other words, instead of changing everything
>> on the path, I can get by with changing things on the ends.
> (Kirsten Chevalier:)
> Perhaps I'm missing something, but I don't see what the problem is here.
> If the state is an abstract data type, then the modules cannot depend
> on how the state is represented. So if we change the type that
> represents the state from State to (State, Counter), nothing
> about B, C, or D changes. If we add new operations getCounter
> and setCounter (of type m Counter and (Counter -> m ()),
> where m is the underlying monad), then A and E can use these
> to manipulate the counter, and the counter is simply ignored by
> B, C and D.
Joachim Durchholz
> Joachim Durchholz wrote:
>
>>It's a property of the concrete language implementation that's being
>>measured here, not a property of the program under the semantics of the
>>language.
>
> Yes indeed. I think this is the key point when considering questions
> like this. Are all Haskell implementations required to yield the same
> instrumentation results for the same program (if the language allowed
> such things)?
There's the question what "same instrumentation results" means.
If it means: "same numbers", then you're measuring a property of the
language, and instrumentation is pointless.
If is means: "equivalent numbers" (e.g. number of times that an
expression was evaluated), then that's an interesting result.
> If not we have ambiguous programs. Now ambiguity may be OK, to find out
> something about the underlying implementation or what transformations and
> optimisations have been implemented (such as the diagnostic examples you
> gave), but somehow I don't think this is what Peter had in mind.
At least the examples that I remember were about counting the number of
calls to a function, which is exactly that kind of instrumentation.
I agree that the results of such instrumentation must not influence the
normal computations. That would indeed be "unsafe" in the
"unsafePerformIO" sense!
One would need some kind of framework to keep the
instrumentation-generated data separate from the other data. A framework
is implicit enough that it doesn't affect all the functions involved in
calling the code being instrumented.
It seems to me that this is what one might call "imperative" (it's
impure, to say the least). However, there's an important point: The
result of every function has two components, a pure one and an
imperative one. As long as I keep the two separate (as in: doing
imperative stuff only for instrumentation purposes or other stuff
unrelated to the pure function application semantics), there's no danger
that the pure component will be "infected" by the impure aspects.
I hope the above description makes sense.
Having instrumentation facilities is actually essential in all
situations where the resource usage of a computation matters. And there
are many cases where this is really important:
* Imagine a purely functional database system (say, a database that
never mutates, like cdb; or a database that never overwrites data, like
Postgres). Such databases analyse queries and cache the analysis
results, some of them even build indexes on the fly if a particular
query comes up often enough. One could hide the state involved in these
activities, but in practice that would be silly since programmers and
database administrators want to take a look into that state and adjust
the heuristics if appropriate. All that we need is that the pure,
state-independent parts of the program are clearly separated from the
state-dependent parts.
* Access over a network. The low-level machinery is quite large and
involved, something that programmers want to debug and administrators
want to monitor. Again, it's not that we want to get rid of that
stateful stuff, we just don't want it to enter into purely functional
stuff like remote function calls which were moved off from the current
machine just for load balancing reasons.
* Load balancing again: a (purely functional) process might trigger the
evaluation of a function call, and some other process might want to
monitor the pogress of that call (e.g. by counting the number of
reductions - that's not perfect but something to show to the impatient
end user). In principle, there's no problem in separating the two
processes, however, they retrieve their information from the same
computation: the "pure" process from the function call's result,
synchronously, in a referentially transparent fashion; the "impure"
process from meta-information about the running evaluation machinery,
asynchronously, in a referentially intransparent fashion.
The snag is: the information that the monitor thread displays is often
best gained by identifying bits and pieces of information within the
function being monitored. In an imperative language, the code being
monitored would call procedures that collect the statistical data in
some locally-global store that the monitoring process can read; how
would that best be done in a functional language?
(I'd like Haskell far better if it offered an answer to that last
question. I don't think that monads are an answer - I suspect they would
require a full rewrite of the function being monitored, aside from the
part that this doesn't help much with the synchronous/asynchronous issue.)
Adrian Hey
> Adrian Hey wrote:
>> Yes indeed. I think this is the key point when considering questions
>> like this. Are all Haskell implementations required to yield the same
>> instrumentation results for the same program (if the language allowed
>> such things)?
>
> There's the question what "same instrumentation results" means.
> If it means: "same numbers", then you're measuring a property of the
> language, and instrumentation is pointless.
Yes, that's what I meant. Should all implementations give the exact same
number for the same program? I think there was an implicit assumption in
Peters original post that this was so, in which case he didn't regard this
as pointless. Though it's hard to be sure, only Peter can resolve this one.
Dunno if Peter's still following this thread.
>> If not we have ambiguous programs. Now ambiguity may be OK, to find out
>> something about the underlying implementation or what transformations and
>> optimisations have been implemented (such as the diagnostic examples you
>> gave), but somehow I don't think this is what Peter had in mind.
>
> At least the examples that I remember were about counting the number of
> calls to a function, which is exactly that kind of instrumentation.
<bare faced cheek mode>
Yes, but take a look at Peters original post. It seems pretty clear
to me (though it's is never explicitly stated) that he's talking about
the pros and cons of various stylistic choices in an imperative language,
and then assuming that the cons of the functional style also apply to
(semantically pure) FPL's.
But maybe you are right, and the purpose of Peter's instrumentation is
to discover something about compiler optimisations, but I see no
evidence of that in what he wrote (and quite a lot of evidence of
imperative assumptions, which also implies no significant compiler
optimisations too).
If I may to be so bold. I would say as general critisism of (what I
understand of) Peters argument is that he doesn't distinguish between
using a "purely function style" in an imperative language and using a
semantically pure (I.E. declarative) FPL.
There is a huge difference between these two IMO. It reminds me of those
folk who refer to FP as a "paradigm", which can be used or not at the
programmers whim in many languages (allegedly).
Using a purely functional style in an imperative language does not
alter the fact that the program is still inherently imperative. So
questions like "what does this function do" or "how many times does
it do it" are still meaningful. But, as Peter observes, the easy
(modular) way to find out involves an awkward departure from the
purely functional style.
Where I take issue with Peter's argument is that this implies that
there is some problem with pure FPL's. In pure FPL semantics the
questions themselves are meaningless IMO, so the fact that I can't
get answers to these questions using the "purely functional style"
imposed by such languages is not a problem at all. It's exactly
what I'd expect from a consistent language design.
The problems start when I try to use unsafePerformIO hackery to
get answers to these meaningless questions. For Haskell I'll likely
get as many different answers as there are Haskell implementations,
maybe even more if I try different optimisation settings.
</bare faced cheek mode>
Regards
--
Adrian Hey
Adrian Hey
> Well, ambiguity is bad. But in fact, a program using unsafePerformIO can
> even crash Haskell. I'm not sure you meant that.
Your right, I didn't mean that, though I won't deny the possibility.
Can you give an example of this? (one where the crashing behaviour
is not caused by the ambiguity of course).
Regards
--
Adrian Hey
Tomasz Zielonka
For example, the following program segfaults when run (compiled with GHC
6.0.1).
import Data.IORef
import System.IO.Unsafe (unsafePerformIO)
ref :: IORef a
ref = unsafePerformIO (newIORef undefined)
main = do
writeIORef ref (1 :: Int)
s <- readIORef ref
print (s :: String)
Joachim Durchholz
> Joachim Durchholz wrote:
>
>> Adrian Hey wrote:
>>
>>> Yes indeed. I think this is the key point when considering
>>> questions like this. Are all Haskell implementations required to
>>> yield the same instrumentation results for the same program (if
>>> the language allowed such things)?
>>
>> There's the question what "same instrumentation results" means. If
>> it means: "same numbers", then you're measuring a property of the
>> language, and instrumentation is pointless.
>
> Yes, that's what I meant. Should all implementations give the exact
> same number for the same program? I think there was an implicit
> assumption in Peters original post that this was so, in which case he
> didn't regard this as pointless.
It's difficult to gues somebody else's mind, but I think it's a
different mode of thinking where this distinction isn't so predominant.
In other words, I think that he was expecting every program to give the
same result, but would reconsider when remembered that the number of
executions may be altered by, say, constant folding.
>>> If not we have ambiguous programs. Now ambiguity may be OK, to
>>> find out something about the underlying implementation or what
>>> transformations and optimisations have been implemented (such as
>>> the diagnostic examples you gave), but somehow I don't think this
>>> is what Peter had in mind.
>>
>> At least the examples that I remember were about counting the
>> number of calls to a function, which is exactly that kind of
>> instrumentation.
>
> <bare faced cheek mode> Yes, but take a look at Peters original post.
> It seems pretty clear to me (though it's is never explicitly stated)
> that he's talking about the pros and cons of various stylistic
> choices in an imperative language, and then assuming that the cons of
> the functional style also apply to (semantically pure) FPL's.
>
> But maybe you are right, and the purpose of Peter's instrumentation
> is to discover something about compiler optimisations,
Not really - I think he's thinking in more general terms.
I.e. instrumentations not to trace just the compiler's work, but to
trace the work of the code in question itself. (Those database backend
and networking examples that I gave.)
There is also the assumption that some things are better done using
imperative code. What I'm missing in his work is considerations for how
and when to cover that imperative stuff under a nice, functional cover.
Maybe he considers that irrelevant because imperative stuff is going to
be controlled in an imperative fashion anyway (e.g. to set and retrieve
hash table overflow ratios and such).
> If I may to be so bold. I would say as general critisism of (what I
> understand of) Peters argument is that he doesn't distinguish between
> using a "purely function style" in an imperative language and using
> a semantically pure (I.E. declarative) FPL.
>
> There is a huge difference between these two IMO. It reminds me of
> those folk who refer to FP as a "paradigm", which can be used or not
> at the programmers whim in many languages (allegedly).
Agreed: functional programming is interesting not only because it gives
a high-level view of iterations and such, it's also interesting because
it gives a lot of guarantees.
However, Peter is well aware of that. The book he's been quoting clearly
expresses that.
I'm not sure how far into automated reasoning he carries the
conclusions; from the book, it seems it's the reasoning of the
programmer who's maintaining the code.
> Where I take issue with Peter's argument is that this implies that
> there is some problem with pure FPL's.
Not really. The issue he finds is different.
There are problems that require massive amounts of code and theory to
get them to work in an FPL. IO is one of these issues, most
self-adapting containers provide another, different case (you can wrap
self-adapting containers in a narrow, pure interface, while the IO
interface remains ugly even if you wrap it in a monad).
His position is that it's useless to insist on purely functional idioms
when their imperative equivalents are just as long, and easier to
understand. (I can find nothing wrong in this idea, I have an issue that
the code examples presented in the book don't distinguish between pure
and impure code. IOW I agree with his "the right tool for the right job"
approach, but I'd like to regain those referential transparency
properties, at least at the library interface level. I haven't seen him
acknowledge that this is an issue, yet.)
> In pure FPL semantics the questions themselves are meaningless IMO,
> so the fact that I can't get answers to these questions using the
> "purely functional style" imposed by such languages is not a problem
> at all. It's exactly what I'd expect from a consistent language
> design.
He is working from a perspective of a hybrid language, with functional
and imperative elements. In such a language, such questions are far from
meaningless even if there's a counter (or some other side-effecting
element) in an otherwise-pure piece of code. In fact, those regions of
code that don't read the counter remain pure even if they call the
function that increments the counter.
Personally, I've been thinking from a hybrid-language perspective where
the compiler is able to infer what code is pure and what code isn't,
possibly with the help of programmer annotations.
I.e. I'd like the advantages of ML and Haskell in one language :-)
Adrian Hey
OK, but how about an example that doesn't exploit the well advertised type
insecurity either :-)
I don't think that's what Andreas was talking about.
Regards
--
Adrian Hey
Daniel Yokomiso
news:51d67993.04012...@posting.google.com...
> Joachim Durchholz <joachim....@web.de> wrote in message
news:<bulq75$4fh$1...@news.oberberg.net>...
> > Peter Van Roy wrote:
> >
> > > [OCaml] has a clean layered structure that allows you to use state
> > > when it's needed. See Appendix D of my book for a more detailed
> > > explanation of why this kind of layered structure is natural:
> > > http://www.info.ucl.ac.be/people/PVR/book.html
> >
> > I think both the book and OCaml get one important detail wrong: the
> > signature of a function gives no warning if it has side effects. In
> > other words, I have to look at the implementations of all functions just
> > to check what logic I can use to reason about a program...
>
> This is an amazingly persistent dogma. I had a long discussion about
> it on the Yahoo pragprog list a few months ago.
Time to reopen old wounds ;)
> It's completely wrong
> for a language to *force you* to say in a function signature whether
> the function internally uses state or not. There are many cases when
> you don't want to say it (and other cases when you *do* want to say
> it, of course).
IIRC the heart of a discussion wasn't if "the function internally uses state
or not" but if the function has hidden side-effects or not.
> It's the responsibility of the function's implementor
> whether or not the function *behaves* as a pure function. If he/she
> says it is so, then you *can* reason about the function as a pure
> function, no matter how it is implemented. If the type system can
> *prove* it is pure, so much the better. But even if it can't, the ability
> to declare the function as pure is an essential one that shouldn't be
> sacrificed on the altar of a weak type system.
In the cited discussion I asserted that a function with type "a -> b" is
inherently different from a function with type "(World, a) -> (World, b)"
(or similar devices) and I wanted the type system to tell me such things.
You disagreed.
> The book considers this so important that it elevates it to a principle:
> the "Model Independence Principle". That is, the externally visible
> interface of a module should not depend on the computation model
> used to implement the module.
> I have thought a lot about the issues and I am personally convinced
> that this principle is correct.
>
> Peter
Best regards,
Daniel Yokomiso.
"this line has five words
and also five syllables
that line had seven"
- Liz Cordingley
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.576 / Virus Database: 365 - Release Date: 30/1/2004
Mark
Wow! A simple question becomes an interesting and extensive thread.
I guess my conclusion will be that the abscence of mutable state does
mean that certain algorithms just can't be expressed, but that the
algorithm can be easily altered so that it can be expressed
functionally with only a slightly larger asymptotic cost.
Thanks to all for such a lively and enlightening discussion.
And a special thanks to Chris Okasaki for actually giving a solution
to my specific problem.
Mark
Adrian Hey
> I guess my conclusion will be that the abscence of mutable state does
> mean that certain algorithms just can't be expressed, but that the
> algorithm can be easily altered so that it can be expressed
> functionally with only a slightly larger asymptotic cost.
Ack! I knew this would happen :-(
Regards
--
Adrian Hey
Mark
Adrian Hey <ah...@NoSpicedHam.iee.org> wrote in message news:<c0e3co$dq2$1$8300...@news.demon.co.uk>...
> Ack! I knew this would happen :-(
Well, the problem right now is that I haven't been able to implement
an O(N) solution to the original problem in Haskell (without using
mutable state). Moreover, nobody has been able to provide their own
O(N) solution.
To me at least, that's evidence in support of the thesis that there
exist algorithms that can't be expressed functionally and non-mutably
with the same asymptotic cost as their imperative implementations.
Now, I really want this thesis to be wrong. So please, somebody show
me an O(N) implementation of randomly permuting a list (or even an
array). (Of course, this will be assuming that array indexing is
O(1), even though I'm now convinced that it isn't.)
To be perfectly honest, every implementation I've come up with has
sucked pretty badly. (Mostly because I'm so new to Haskell and
functional programming.) I'd love to see a few good Haskell
implemented solutions to the problem even if they are O(NlogN).
Mark
Darius
mf...@cpsc.ucalgary.ca (Mark) wrote:
> Greetings,
>
> Adrian Hey <ah...@NoSpicedHam.iee.org> wrote in message
> news:<c0e3co$dq2$1$8300...@news.demon.co.uk>...
> > Ack! I knew this would happen :-(
>
> Well, the problem right now is that I haven't been able to implement
> an O(N) solution to the original problem in Haskell (without using
> mutable state). Moreover, nobody has been able to provide their own
> O(N) solution.
>
> To me at least, that's evidence in support of the thesis that there
> exist algorithms that can't be expressed functionally and non-mutably
> with the same asymptotic cost as their imperative implementations.
>
> Now, I really want this thesis to be wrong. So please, somebody show
> me an O(N) implementation of randomly permuting a list (or even an
> array). (Of course, this will be assuming that array indexing is
> O(1), even though I'm now convinced that it isn't.)
Array indexing, as in lookup, is as O(1) in Haskell as it is in any
other language.
Joachim Durchholz
>
> Well, the problem right now is that I haven't been able to implement
> an O(N) solution to the original problem in Haskell (without using
> mutable state).
Array indexing is actually O (log N).
Well, it's O (1) if you limit memory size - but if you have any limits,
big-Oh metric becomes inapplicable.
And if you assume unlimited resources, an increasing array size will
spill into progressiver slower memory: L2 cache, RAM, virtual memory,
magnetic tape, whatever.
I don't think that distinguishing between O (1) and O (log N) is very
practical; constant factors play a far larger role. Besides, even if you
are able to pin down the constant factors (*very* hard and *very* rarely
done), log N factors tend to be swamped in statistical noise.
> I guess my conclusion will be that the abscence of mutable state does
> mean that certain algorithms just can't be expressed,
Some algorithms don't translate in a straightforward manner.
Just as with OO. Or logic programming. Or dataflow.
Nothing new here :-)
Adrian Hey
Well first off I would like to say that it's a big leap from saying
something can't be done in Haskell (which may or may not be true) to
saying it can't be done in any (pure) FPL.
I also think you need be careful about exactly what you mean by "using
mutable state". Here's my translation of Torbens array based solution
to ST monad..
import Control.Monad.ST(ST,runST)
import Data.Array.ST(STArray)
import Data.Array.MArray(newListArray,readArray,writeArray)
-- p = 0..(n!-1) where n = length xs
permute :: Int -> [x] -> [x]
permute p xs = let n = length xs
in runST (do array <- newListArray (0,n-1) xs
permuteST n p array)
permuteST :: Int -> Int -> STArray s Int x -> ST s [x]
permuteST 1 0 array = do x <- readArray array 0
return [x]
permuteST n p array = let (p',i) = p `divMod` n
n' = n-1
in do x <- readArray array i
t <- readArray array n'
writeArray array i t
xs <- permuteST n' p' array
return $ x:xs
[I should make the trivial observation that this is not a practical
solution for anything other than fairly short lists (the p argument
should really be an Integer).]
Then there's the issue of those pesky log N factors. Is array access really
consant time? and what about those arithmetic operations? I say we don't
need to be concerned about this because whatever view you take the answer is
surely not dependent on whether an imperative language or pure FPL is used
to implement the above algorithm (provided the cost of arithmetic and array
operations is the same in both languages of course).
I think the questions of interest are..
1- Does this solution use mutable state.
2- Is using mutable state incompatible with pure FP.
My answer to (1) would be semantically NO, but pragmatically YES.
The real purpose of the ST monad here is to enforce a single theaded use
of the array so that the underlying (pragmatic) array implementation can
be mutable. But that's just the Haskell way, and the Haskell way isn't
necessarily the only way. Clean uses uniqueness typing and any FPL
implementation could make use of uniqueness analysis in it's optimisations
but not have uniqueness typing part of the (visible) type sytstem.
My answer to (2) would be semantically YES, but pragmatically NO. All
"purely functional" programming languages ultimately rely on mutable
state for their implementation. If they can still be regarded as
purely functional then there seems to be no justification for picking
on a particular data type (such arrays) for special treatment, if they
are used in a manner which preserves referential transparency.
My 2p..
Regards
--
Adrian Hey