Space leaks etc.
Nick Williams
The bit of code (in Haskell) that follows is part of some graph
algorithm related work I am doing at the moment.
It's supposed to build a tree of trees to allow O(log |V|) access
to the weights of edges in a directed graph, G=(V,E). On my
analysis, the expected asymptotic runtime is O(|E| log |V|)...
However, it's taking a _very_ long time to run on large graphs,
rather worse than I would've expected. It's also using
astonishing amounts of memory. On a test graph with 5,000
vertices and 250,000 edges, it used 176MB of RAM.
Two questions: firstly, have I missed something in my analysis
of its running time? Secondly, why is it using so much memory?
Is this the price I am paying for persistence of data
structures?
[code follows - thanks]
type Cost = Int
type Vertex = Int
type Edge = (Vertex,Vertex)
type EdgePlus=(Vertex,Vertex,Cost)
data STree a = Null | Fork (STree a) a (STree a) deriving Show
type WTree = STree (Vertex, STree(Vertex, Cost))
buildweight :: [EdgePlus] -> ([Edge],WTree)
buildweight eps = foldr bw ([],Null) eps
bw :: EdgePlus -> ([Edge], WTree) -> ([Edge], WTree)
bw e@(v1,v2,w) (es, Null) = ((v1,v2):es,
Fork Null (v1, Fork Null (v2,w) Null) Null)
bw e@(v1,v2,w) (es, Fork xt (x,t) yt)
| v1 == x = (found_es, Fork xt (x,found_t) yt)
| v1 < x = (less_es, Fork less_t (x,t) yt)
| v1 > x = (more_es, Fork xt (x,t) more_t)
where (less_es,less_t) = bw e (es,xt)
(more_es,more_t) = bw e (es,yt)
(found_es,found_t) = bw2 e (es,t)
bw2 :: EdgePlus -> ([Edge], STree (Vertex,Cost)) ->
([Edge], STree (Vertex,Cost))
bw2 e@(v1,v2,w) (es, Null) = ((v1,v2):es,Fork Null (v2,w) Null)
bw2 e@(v1,v2,w) (es, Fork xt (v,cw) yt)
| v2 == v = if w<cw then (es, Fork xt (v,w) yt)
else (es, Fork xt (v,cw) yt)
| v2 < v = (less_es, Fork less_t (v,cw) yt)
| v2 > v = (more_es, Fork xt (v,cw) more_t)
where (less_es,less_t) = bw2 e (es,xt)
(more_es,more_t) = bw2 e (es,yt)
--
[ Nick Williams ]
[ MSc Computation Mobile - 07957-138179 ]
[ New College, Oxford http://www.new.ox.ac.uk/~nick/ ]
Tommy Thorn
> Hiya everyone...
>
> The bit of code (in Haskell) that follows is part of some graph
> algorithm related work I am doing at the moment.
Which implementation? GHC, Hugs, NHC, HBC, ...?
> It's supposed to build a tree of trees to allow O(log |V|) access
> to the weights of edges in a directed graph, G=(V,E). On my
> analysis, the expected asymptotic runtime is O(|E| log |V|)...
Be _very_ careful with complexity analysis of call-by-need programs.
You must have a very good understanding of the operational semantics
for this to be meaningful. And the operational semantics depends on
the compiler to some extend.
> However, it's taking a _very_ long time to run on large graphs,
> rather worse than I would've expected. It's also using
> astonishing amounts of memory. On a test graph with 5,000
> vertices and 250,000 edges, it used 176MB of RAM.
First thing to do is the bring down the memory consumption. In
general you could use NHC with it's advance space profiler.
> Two questions: firstly, have I missed something in my analysis
> of its running time? Secondly, why is it using so much memory?
The two are likely strongly related.
> Is this the price I am paying for persistence of data structures?
I've only glanched at the code snipped below, but it looks like you
don't need lazyness, so one thing you might do is to make STree
strict, that is
> data STree a
> = Null
> | Fork ! (STree a) ! a ! (STree a)
> deriving Show
This might have a rather drastic effect in cutting down the number of
closures created and should improve your run time in this case.
Let us know,
Tommy
--
"Microsoft shouldn't be broken up. It should be shut down."
-- Security expert Bruce Schneier on the ILOVEYOU virus.
Daniel C. Wang
Tommy Thorn <th...@brics.dk> writes:
> ni...@thelonious.new.ox.ac.uk (Nick Williams) writes:
> > Hiya everyone...
> >
> > The bit of code (in Haskell) that follows is part of some graph
> > algorithm related work I am doing at the moment.
>
> Which implementation? GHC, Hugs, NHC, HBC, ...?
>
> > It's supposed to build a tree of trees to allow O(log |V|) access
> > to the weights of edges in a directed graph, G=(V,E). On my
> > analysis, the expected asymptotic runtime is O(|E| log |V|)...
>
> Be _very_ careful with complexity analysis of call-by-need programs.
> You must have a very good understanding of the operational semantics
> for this to be meaningful. And the operational semantics depends on
> the compiler to some extend.
<flame bait>
Oh really, I thought call-by-need was the best things since slice
bread.... and made reasoning about your programs easier.....
The real answer to the posters problem is that he ought to be programming in
a language.... where call-by-value is the default behavior and laziness is
an option....
</flame bait>
So, can someone fill me in on the details of stricness support in Haskell?
Can you only annotate data constructors as strict? It would be nice to see
support in Haskell for strict functions. In a way similar to the purposed
lazy extensions to ML, one could even add a new function type to distinguish
between strict and non-strict functions in module signatures....
It would be very nice to be able to write Haskell that doesn't use laziness
at all and still have my programs look relatively nice.
Nick Williams
Tommy Thorn <th...@brics.dk> wrote:
>> The bit of code (in Haskell) that follows is part of some graph
>> algorithm related work I am doing at the moment.
>
>Which implementation? GHC, Hugs, NHC, HBC, ...?
It's GHC... and it's interesting that you ask: if I post a
question about C to comp.lang.c asking about a snippet of code
that agrees with ANSI c, no-one asks me which compiler I am
using...
>> It's supposed to build a tree of trees to allow O(log |V|) access
>> to the weights of edges in a directed graph, G=(V,E). On my
>> analysis, the expected asymptotic runtime is O(|E| log |V|)...
>
>Be _very_ careful with complexity analysis of call-by-need programs.
>You must have a very good understanding of the operational semantics
>for this to be meaningful. And the operational semantics depends on
>the compiler to some extend.
I'm aware of the trickiness involved in complexity analysis with
regard to lazy semantics; however, surely the worst-case
asymptotic complexity for a lazy algorithm should be no worse
than that of an otherwise-semantically-identical strict
algorithm? In a perfect world at least?
[snip suggestions wrt making some strictness annotations]
I'll try that, and also some heap profiling.
Cheers,
Nick.
Nick Williams
Daniel C. Wang <danwan...@cs.princeton.edu> wrote:
><flame bait>
>Oh really, I thought call-by-need was the best things since slice
>bread.... and made reasoning about your programs easier.....
<grin> Quite often, it does, but when you're translating
imperative algorithms into functional ones for pedagogic
purposes, it can trip you up.
>So, can someone fill me in on the details of stricness support in Haskell?
>Can you only annotate data constructors as strict? It would be nice to see
>support in Haskell for strict functions. In a way similar to the purposed
>lazy extensions to ML, one could even add a new function type to distinguish
>between strict and non-strict functions in module signatures....
As you know, (f x) is lazy functional application in Haskell: (f
$ x) is the same thing, and if you want strict application, then
you can write (f $! x). They've both got low, right-associative
precedence, so you can write (f $ g $ x) rather than (f (g x)).
Daniel C. Wang
ni...@thelonious.new.ox.ac.uk (Nick Williams) writes:
> In article <r8t8zwk...@vista.cs.princeton.edu>,
> Daniel C. Wang <danwan...@cs.princeton.edu> wrote:
>
> ><flame bait>
> >Oh really, I thought call-by-need was the best things since slice
> >bread.... and made reasoning about your programs easier.....
>
> <grin> Quite often, it does, but when you're translating
> imperative algorithms into functional ones for pedagogic
> purposes, it can trip you up.
This is not an issue of imperative vs. functional it call-by-name
vs. call-by-value.
>
> >So, can someone fill me in on the details of stricness support in Haskell?
> >Can you only annotate data constructors as strict? It would be nice to see
> >support in Haskell for strict functions. In a way similar to the purposed
> >lazy extensions to ML, one could even add a new function type to distinguish
> >between strict and non-strict functions in module signatures....
>
> As you know, (f x) is lazy functional application in Haskell: (f
> $ x) is the same thing, and if you want strict application, then
> you can write (f $! x). They've both got low, right-associative
> precedence, so you can write (f $ g $ x) rather than (f (g x)).
While this is nice. It would be nicer to be able to *declare* a function to
be strict, so I don't have to use $! all over the place...
lazy fun f x:t = ....
is one purposed ML extension which delays arguments to f.
Other wise I'd have to write (f (fn () => e)) all over the place. Haskell,
is making me do the same but only with $ to figure out what things are strict.
This has the other advantage that I can write my progam in a lazy style,
then make it strict by mucking with the declarations one by one, until I get
what I expect, without having to sprinkle my code with $.
This is almost an issue of syntax... but a pretty important one... as
without good syntactic support, strictness annotations will just not get
use.. because they are a pain.
Daniel C. Wang
ni...@thelonious.new.ox.ac.uk (Nick Williams) writes:
> I'm aware of the trickiness involved in complexity analysis with
> regard to lazy semantics; however, surely the worst-case
> asymptotic complexity for a lazy algorithm should be no worse
> than that of an otherwise-semantically-identical strict
> algorithm? In a perfect world at least?
This is true for the time complexity. It is not true for the space
complexity. As you have discovered...
Nick Williams
Daniel C. Wang <danwan...@cs.princeton.edu> wrote:
>> >Oh really, I thought call-by-need was the best things since slice
>> >bread.... and made reasoning about your programs easier.....
>> <grin> Quite often, it does, but when you're translating
>> imperative algorithms into functional ones for pedagogic
>> purposes, it can trip you up.
>This is not an issue of imperative vs. functional it call-by-name
>vs. call-by-value.
You're remarkably insightful if you can tell what the issues
involved in what I'm doing are, when you know virtually nothing
about it.
The algorithm which I am transliterating (I suspect that word is
closer to the truth than translating) can make no good use of
laziness at data constructor level, so there is some overheard
in creating the closures that were necessary for laziness. Since
I am dealing with quite large cases of the problem, any
performance tweaks are obviously A Good Thing.
>While this is nice. It would be nicer to be able to *declare* a function to
>be strict, so I don't have to use $! all over the place...
It sounds like you want to be writing in a strict FPL :-)
>This is almost an issue of syntax... but a pretty important one... as
>without good syntactic support, strictness annotations will just not get
>use.. because they are a pain.
To be honest, I think the current Haskell options of strictness
notations in datatype constructors or using (f $! x) to indicate
strict application are sufficient: I guess it comes down to a
matter of opinion, and style.
Albert Lai
From: tre...@vex.net (Albert Y. C. Lai)
Date: 05 Jun 2000 14:19:11 -0400
Message-ID: <m366rod...@career.localdomain>
Lines: 76
X-Newsreader: Gnus v5.6.45/XEmacs 21.1 - "Arches"
> It's GHC... and it's interesting that you ask: if I post a
> question about C to comp.lang.c asking about a snippet of code
> that agrees with ANSI c, no-one asks me which compiler I am
> using...
I would wager that when C was just 10 years old, C programmers had to
tell each other which compilers they were using in order to discuss
code.
I would also guess that the C questions you ask are not about temporal
or spatial behaviour, but just about input-output behaviour.
Afterall, the C standard does not specify time or space bounds. If
you did ask a temporal or spatial question and no one cared which
compiler you used, that only means they were plain wrong. More on
this in the postscript.
> I'm aware of the trickiness involved in complexity analysis with
> regard to lazy semantics; however, surely the worst-case
> asymptotic complexity for a lazy algorithm should be no worse
> than that of an otherwise-semantically-identical strict
> algorithm? In a perfect world at least?
This is correct for amortized or begin-to-end time complexity. It is
easy to find counterexamples for space complexity and fine-grained
time complexity. Here is one:
foldl (+) 0
This function sums up a list. If the list is finite with n elements,
The time complexity is O(n) additions, regardless of evaulation
policies. However, when it comes to space complexity, eager
evaluation will take O(1) space and lazy evaluation will take O(n)
space.
Fine-grained time complexities also differ. With strict evaluation,
as soon as foldl finishes we are done. With lazy evaluation, after
foldl finishes there is still an O(n)-long chain of additions to
evaluate.
P.S.
The asymptotic running time of the following ANSI C code depends on
the compiler:
int i, j, t;
for (i = 0; i < N; ++i) {
t = 1;
for (j = 1; j <= N; ++j) {
t = t * j;
}
}
The asymptotic space usage of the following ANSI C function should
depend on the compiler:
int f(int s, int n)
{
if (n == 0)
return s;
else
return f(s*n, n-1);
}
It interesting to note that if we translate it into a functional
language and ask on comp.lang.functional, the unanimous answer is O(1)
if the language is strict. It almost does not matter which language
it is, let alone which compiler is used.
C is not as standardized as you thought, and functional language
implementations are not as fragmented as you make out.
--
[If you post a response, no need to cc me; if you cc me, please say so.]
"The best theory is inspired by practice.
The best practice is inspired by theory." - Donald E. Knuth
Tommy Thorn
> It's GHC... and it's interesting that you ask: if I post a
> question about C to comp.lang.c asking about a snippet of code
> that agrees with ANSI c, no-one asks me which compiler I am
> using...
Appels and Oranges. The semantics of C is trivial (in comparison),
all compilers have _mostly_ the same semantics (however beware of
stuff like `f(x++)').
Now your question was on a purely operational aspect. Any of the
Haskell implementations mentioned would have given the same _result_
but they are likely to use a different amount of time and space.
Given the vast liberty of _how_ to evaluate lambda expressions, why
would that surprise you?
Naturally when I ask which implementation it is because each have its
own strong points, peculiarities, and set of tools.
> I'm aware of the trickiness involved in complexity analysis with
> regard to lazy semantics; however, surely the worst-case
> asymptotic complexity for a lazy algorithm should be no worse
> than that of an otherwise-semantically-identical strict
> algorithm? In a perfect world at least?
That is true to some extent, but mostly irrelevant. In the Real
World, the lazy semantics can have an order of magnitude impact on the
time behaviour due to the overhead of suspensions, increased paging,
etc. Sometimes you win, sometimes you loose. For the loosing case,
you can always annotate the program all the way to strict semantics.
Going in the opposite direction is much harder.
In my experience, trying to retrofit a strict algorithm directly often
leads to these kind of surprises, but I'd still recommend your staying
with Haskell. I'd be rather surprised if a little strictness
annotation won't suffice to bring the result in line with one you
would expect from an SML implementation. Unless, of course, your
analysis is flawed.
/Tommy
Daniel C. Wang
{stuff deleted}
> Now your question was on a purely operational aspect. Any of the
> Haskell implementations mentioned would have given the same _result_
> but they are likely to use a different amount of time and space.
> Given the vast liberty of _how_ to evaluate lambda expressions, why
> would that surprise you?
<flame>
This utter hog wash. It is a deficiency in the language standard if I can't
write reasonable programs that are "performance portable". Don't give some
"declarative programming" hog wash either. Even Prolog has a well defined
operational semantics independent of compiler implementations.
What's the point of a language standard, if it doesn't give you a reasonable
performance model? The Scheme standard requires proper
tail-recursion. People, write Scheme programs using tail-recursion and
expect the conforming implementations to "do the right thing". Why should
not Haskell be any different with respect to evaluation order.
</flame>
> Naturally when I ask which implementation it is because each have its
> own strong points, peculiarities, and set of tools.
<flame>
i.e. I can't write portable Haskell programs...
</flame>
> That is true to some extent, but mostly irrelevant. In the Real
> World, the lazy semantics can have an order of magnitude impact on the
> time behaviour due to the overhead of suspensions, increased paging,
> etc. Sometimes you win, sometimes you loose. For the loosing case,
> you can always annotate the program all the way to strict semantics.
> Going in the opposite direction is much harder.
<claim>
Converting a strict program into a non-strict program is as easy as doing
the reverse. You are kidding yourself if you think otherwise.
Rather the putting "$" everywhere I insert forces and delays, everywhere.
http://cm.bell-labs.com/cm/cs/who/wadler/papers/lazyinstrict/lazyinstrict.ps.gz
Although Phil Wadler makes a good point about odd vs. even programming
styles, he then goes on to show how to add laziness to strict programming
languages which makes it quite easy to turn strict programs in to lazy ones.
</claim>
> In my experience, trying to retrofit a strict algorithm directly often
> leads to these kind of surprises, but I'd still recommend your staying
> with Haskell. I'd be rather surprised if a little strictness
> annotation won't suffice to bring the result in line with one you
> would expect from an SML implementation. Unless, of course, your
> analysis is flawed.
<flame>
In your experience laziness makes it difficult to reason about programs in a
natural way.
</flame>
Okay... I've beat this topic to death. This just a pet peeve of mine, not
because I think SML or call-by-value is the way to go. It's because so many
FP people seem to continually sing the praises of laziness without
acknowledging that it is not a panacea. A decent programming language should
support both styles of programming well. Unfortunately, I don't know of any
programming language in wide spread use that does.
Nick Williams
>> It's GHC... and it's interesting that you ask: if I post a
>> question about C to comp.lang.c asking about a snippet of code
>> that agrees with ANSI c, no-one asks me which compiler I am
>> using...
>I would wager that when C was just 10 years old, C programmers
>had to tell each other which compilers they were using in order
>to discuss code.
I'm sorry if you took me wrong when I said this: this wasn't
meant as a snide comment about the state of development of
functional compilers: it was honestly meant as an interesting
aside: those who read c.l.c will recognise it as a den of
pedantry, but the question as to a compiler would not be one
that would be brought up.
>> I'm aware of the trickiness involved in complexity analysis
>> with regard to lazy semantics; however, surely the worst-case
>> asymptotic complexity for a lazy algorithm should be no worse
>> than that of an otherwise-semantically-identical strict
>> algorithm? In a perfect world at least?
>This is correct for amortized or begin-to-end time complexity.
>It is easy to find counterexamples for space complexity and
>fine-grained time complexity.
Sorry if I failed to make it clear that I was talking about
amortized time bounds, rather than any other sort: the original
comment was in the context of the overall run-time of an
algorithm.
>C is not as standardized as you thought, and functional
>language implementations are not as fragmented as you make out.
It was not my intention to make this comparison: I apologise if
it came across this way.
Nick Williams
Tommy Thorn <th...@brics.dk> wrote:
>Appels and Oranges. The semantics of C is trivial (in comparison),
>all compilers have _mostly_ the same semantics (however beware of
>stuff like `f(x++)').
You can take that comment into comp.lang.c and you'll either get
a) an answer quoted from chapter and verse of the ISO C standard
or b) flamed for using 'undefined behaviour'. <grin>
>Now your question was on a purely operational aspect. Any of
>the Haskell implementations mentioned would have given the same
>_result_ but they are likely to use a different amount of time
>and space. Given the vast liberty of _how_ to evaluate lambda
>expressions, why would that surprise you?
Honestly, it doesn't surprise me: please read my other post in
this thread for an explanation: by way of summary, this wasn't
meant as implied criticism, it was merely an aside that only
really makes much sense if you've read comp.lang.c for a while.
>In my experience, trying to retrofit a strict algorithm
>directly often leads to these kind of surprises, but I'd still
>recommend your staying with Haskell. I'd be rather surprised
>if a little strictness annotation won't suffice to bring the
>result in line with one you would expect from an SML
>implementation. Unless, of course, your analysis is flawed.
Since what I'm trying to achieve is a comparison between a
number of different styles of programming in functional
languages, this sort of surprise is exactly what I'm interested
in: I'm comparing implementations of 'purely imperative'
algorithms (those which seem to require essential use of arrays
and/or destructive updates) in purely functional Haskell and ML,
and also in monadic style (using mutable arrays and state
monads), and making use of the impure features of ML.
Thanks for your comments: it wasn't my intention to start a
flamewar, which is what I seem unwittingly to have achieved.
Daniel C. Wang
ni...@thelonious.new.ox.ac.uk (Nick Williams) writes:
{stuff deleted}
> Thanks for your comments: it wasn't my intention to start a
> flamewar, which is what I seem unwittingly to have achieved.
> Since what I'm trying to achieve is a comparison between a
> number of different styles of programming in functional
> languages, this sort of surprise is exactly what I'm interested
> in: I'm comparing implementations of 'purely imperative'
> algorithms (those which seem to require essential use of arrays
> and/or destructive updates) in purely functional Haskell and ML,
> and also in monadic style (using mutable arrays and state
> monads), and making use of the impure features of ML.
So is this going to get written up for general consumption? I'm quite
curious.
> Thanks for your comments: it wasn't my intention to start a
> flamewar, which is what I seem unwittingly to have achieved.
The flame war not your fault.... :)
Koen Claessen
| While this is nice. It would be nicer to be able to
| *declare* a function to be strict, so I don't have to
| use $! all over the place...
How about:
fLazy x = ...
fStrict x = fLazy $! x
It cannot be done easier...
| Converting a strict program into a non-strict program
| is as easy as doing the reverse. You are kidding
| yourself if you think otherwise.
What do you mean by a "strict program" and a "lazy
program"? A lazy program is, presumably, a pogram that uses
laziness in some way. This is not the same as the program
being written in a lazy language.
Just adding a delay/force kind of mechanism to a language
does not make it easier to change a strict algorithm into an
algorithm that uses laziness in some way.
| [...] It's because so many FP people seem to
| continually sing the praises of laziness without
| acknowledging that it is not a panacea.
I don't think this is true. Ask any Haskell programmer and
they'll say that their choice of language was a trade-off
between the clarity and modularity of programming style on
one hand, and the difficulty of reasoning about operational
behavior on the other.
People are working on semantic foundations of reasoning
about space behavior of call-by-need programs [1]. One day,
hopefully, this will be the basis of a compiler/tool that
can help a programmer avoid or track down space bugs more
easily.
| A decent programming language should support both
| styles of programming well. Unfortunately, I don't
| know of any programming language in wide spread use
| that does.
That programming language will have exactly the same
problems with operational behavior as Haskell has. You can
only reason about this today, if you have a thorough
understanding of what laziness is.
Regards,
Koen.
--
Koen Claessen http://www.cs.chalmers.se/~koen
phone:+46-31-772 5424 mailto:ko...@cs.chalmers.se
-----------------------------------------------------
Chalmers University of Technology, Gothenburg, Sweden
Daniel C. Wang
{stuff deleted}
> What do you mean by a "strict program" and a "lazy
> program"? A lazy program is, presumably, a pogram that uses
> laziness in some way. This is not the same as the program
> being written in a lazy language.
Let me clarify. It is as easy/hard to write a strict program in a language
where laziness is the default behavior, as it is to write a program that
uses laziness in a language that is strict by default.
My other point is that strict is as useful as lazy.
> I don't think this is true. Ask any Haskell programmer and
> they'll say that their choice of language was a trade-off
> between the clarity and modularity of programming style on
> one hand, and the difficulty of reasoning about operational
> behavior on the other.
Strictness is not at odds with clarity or modularity. This "trade-off" that
you talk about doesn't really exists. You can have both strict and lazy
styles of programming at the same time.
{stuff deleted}
> | A decent programming language should support both
> | styles of programming well. Unfortunately, I don't
> | know of any programming language in wide spread use
> | that does.
>
> That programming language will have exactly the same
> problems with operational behavior as Haskell has. You can
> only reason about this today, if you have a thorough
> understanding of what laziness is.
You miss the point. Haskell, by default chooses to make everything
implicitly lazy. This "default" makes it difficult to reason about
operational behavior. A programming language where I can program with a
simple to understand operational model and also supports a programming style
which is more declarative/lazy would be a better languge. Then a language
which makes a "trade-off".
Paul Hudak
Suppose I have this code fragment:
if pred then complexexpression1
else complexexpression2
and then I decide, wearing my "clarity and modularity hat",
to rewrite it as:
let x1 = complexexpression1
x2 = complexexpression2
in if pred then x1 else x2
In a strict language I may have changed the meaning of the program.
This seems "at odds with clarity [and] modularity" to me.
On the other hand, I can more easily reason about the complexity of the
latter program if it were strict (because everything is evaluated),
whereas with a lazy language I need to know the value of pred.
This is the tradeoff. Choose your poison.
(Designing a language with both evaluation mechanisms just allows you to
choose the poison many different times :-)
-Paul
Daniel C. Wang
Paul Hudak <paul....@yale.edu> writes:
> > Strictness is not at odds with clarity or modularity.
>
> Suppose I have this code fragment:
>
> if pred then complexexpression1
> else complexexpression2
>
> and then I decide, wearing my "clarity and modularity hat",
> to rewrite it as:
>
> let x1 = complexexpression1
> x2 = complexexpression2
> in if pred then x1 else x2
>
> In a strict language I may have changed the meaning of the program.
> This seems "at odds with clarity [and] modularity" to me.
This is a bogus example. It's comparing appels to oranges. It like saying
look if I rewrite (1+2) as 4 my program is now different.
The right way to rewrite the above is
let fun x1 () = complexexpression1
fun x2 () = complexexpression2
in if pred then x1() else x2()
This rewrite preservers the semantics, and is only just a little more
syntactically clumsy than the previous one. For most progammers, it also
makes it perfectly clear when the expressions maybe evaluated.
(Note this rewrite is guaranteed to preserver semantics regardless of the
underlying evaluation technique used by the programming language.)
I've seen exactly this example too many times... and I used to think there
was something deep going on about this.... but if you really think about it
all boils down to an issue of syntax.
The issue here is what rules of equality may I use to reason about my
program. The lazy/pure/referentially transparent languages let me use the
normal Beta rule from the pure lambda calculus. In an impure and strict
functional programming language, I'm l limited to using the Beta-value rule
to reason about program equality.
I don't see why the Beta rule is some how inherently more "modular or clear"
then the Beta-value rule. The majority or real programmers are quiet used to
using the Beta-value rule all the time.
> On the other hand, I can more easily reason about the complexity of the
> latter program if it were strict (because everything is evaluated),
> whereas with a lazy language I need to know the value of pred.
> This is the tradeoff. Choose your poison.
> (Designing a language with both evaluation mechanisms just allows you to
> choose the poison many different times :-)
Those of us who wish to commit suicide should be given a choice how we do
it. :)
Also as a matter of practice the lazy/pure/referentially transparent
features of Haskell, make it difficult to write modular programs, because I
cannot hide effects behind an abstract interface.
For example, if I have a balanced binary search tree interface that is
implemented with red-black trees. I can not replace my red-black tree
implementation with a splay tree implementation and still use the same
interface, because splay trees require one mutable reference to guarantee
their asymptotic performance.
Using that one mutable reference in Haskell, would require me to change my
balanced binary search tree interface to expose this fact so that my splay
tree uses the appropriate monad. Whats worse all my client code has to be
rewritten with "do " notation. So changing the implementation of my balanced
binary search tree module requires me to modify my whole program. This is at
odds with "modular" programming.
SML used to have this same problem with "imperative type variables", where
the use of an imperative feature "beneath the hood" would have to be made
externally visible in the interface. Once the value restriction was
added to SML97 and imperative type variables went away ML became more
modular.
This example is only marginally related to the issue of laziness, but
the Haskell designers have bent over backward to maintain referential
transparency (i.e. use of normal Beta rule to prove program equivalence)
and I really can't see why they went through all the trouble.
Forcing programmers or compiler* to use the Beta-v rules rather than the
Beta rule isn't that hard, and in return you get an operational semantics
that is much more easy to reason about.
*Note if you CPS transform your programs the Beta and Beta-v rules are
equivalent. So for compilers it is trivial to use either rule....
Let me not sound like I'm bashing Haskell. There are lots of features in
Haskell I like, but there are lots of things I could do without.
Marcin 'Qrczak' Kowalczyk
> Also as a matter of practice the lazy/pure/referentially transparent
> features of Haskell, make it difficult to write modular programs,
> because I cannot hide effects behind an abstract interface.
>
> For example, if I have a balanced binary search tree interface
> that is implemented with red-black trees. I can not replace my
> red-black tree implementation with a splay tree implementation
> and still use the same interface, because splay trees require one
> mutable reference to guarantee their asymptotic performance.
You can, provided that you don't mind using features that are not
(yet) in the standard. The ST monad can be safely wrapped in a pure
computation.
From: Koen Claessen <ko...@cs.chalmers.se>
Subject: Re: "Boxed imperatives" to implement pure functions
Date: Tue, 6 Jun 2000 16:16:39 +0200 (MET DST)
Message-ID: <Pine.SOL.4.21.000606...@muppet23.cs.chalmers.se>
Cc: The Haskell Mailing List <has...@haskell.org>
Bjarke Dahl asked:
| Has anyone made a generalization of accumArray, which
| allows users to implement a pure function using
| imperative features?
Take a look at the ST monad, implemented in most
(all?) Haskell compilers.
Relevant papers are:
"Lazy Functional State Threads"
John Launchbury & Simon Peyton Jones
"Structuring Depth First Search Algorithms in Haskell"
David King & John Launchbury
The last paper is one of the nicest papers I have ever read,
it describes many depth-first search graph algorithms in a
functional style, and proves their correctness using
algebraic methods.
Both are available from:
http://www.cse.ogi.edu/~jl/biblio-functional.html
Regards,
Koen.
--
Koen Claessen http://www.cs.chalmers.se/~koen
phone:+46-31-772 5424 mailto:ko...@cs.chalmers.se
-----------------------------------------------------
Chalmers University of Technology, Gothenburg, Sweden
--
__("< Marcin Kowalczyk * qrc...@knm.org.pl http://qrczak.ids.net.pl/
\__/ GCS/M d- s+:-- a23 C+++$ UL++>++++$ P+++ L++>++++$ E-
^^ W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP+ t
QRCZAK 5? X- R tv-- b+>++ DI D- G+ e>++++ h! r--%>++ y-
Amr A Sabry
>
> Also as a matter of practice the lazy/pure/referentially transparent
> features of Haskell, make it difficult to write modular programs,
because I
> cannot hide effects behind an abstract interface.
I used to have the same criticism of Haskell (and ML's imperative
type variables) but now I actually believe that it is the right thing to
do to
expose effects in the types of expressions.
The issue goes beyond Haskell and ML. Consider how checked exceptions
in Java must be made visible in the types of methods. I believe this
was
a good design decision, even though it does prevent you from replacing
code that does not throw exceptions by code that might.
One of the main lessons of monads is that if an expression may have
effects
then the type of the expression should reflect this. As you note: there
is a
cost to this additional precision. One can no longer naively
interchange pieces
of code that use different effects. But the general remedy is to
develop
mechanisms for "encapsulating effects" using technologies like
type-and-effect
systems.
--
Amr Sabry Phone : +1 (541) 346-4411
Department of Computer & Information Science Fax : +1 (541) 346-5373
Deschutes Hall, University of Oregon email : sa...@cs.uoregon.edu
Eugene OR 97403-1202, USA http://www.cs.uoregon.edu/~sabry
The real contest is always between what you've done and what you're
capable of doing. You measure yourself against yourself and nobody
else. - Geoffrey Gaberino
Daniel C. Wang
qrc...@knm.org.pl (Marcin 'Qrczak' Kowalczyk) writes:
> 06 Jun 2000 17:43:48 -0400, Daniel C. Wang <danwan...@cs.princeton.edu> pisze:
>
> > Also as a matter of practice the lazy/pure/referentially transparent
> > features of Haskell, make it difficult to write modular programs,
> > because I cannot hide effects behind an abstract interface.
> >
> > For example, if I have a balanced binary search tree interface
> > that is implemented with red-black trees. I can not replace my
> > red-black tree implementation with a splay tree implementation
> > and still use the same interface, because splay trees require one
> > mutable reference to guarantee their asymptotic performance.
>
> You can, provided that you don't mind using features that are not
> (yet) in the standard. The ST monad can be safely wrapped in a pure
> computation.
I just took a peek at the lazy state thread work. It doesn't solve all of
the problem. Lazy state threads let me run a stateful computation and then
use it's result in a pure setting.
But consider
type Map a
insert :: Map a -> a -> Map a
What I'm complaining about is simply the fact the type of insert gurantees
me that it has "no-side observable effects". Even if I used the ST monad
and lazy state threads internally this property is preserved. (Which is
quiet cool...)
However for Splay trees I must have an interface of the form
insert :: ST (Map a) -> a -> ST (Map a)
because the splay trees must use side effects and the effect *must be
observerable outside* of insert in order to get the amortized performance
neccessary.
Here's a better example... I have a pure interface, and for debugging or
profiling reasons, every time I call a function I want it to write an entry
to a log file. In order to do this I have to use unsafePreformIO or muck
with my interface and rewrite all my code that uses my pure interface, so
that it uses a monadic interface. If I didn't have "unsafePreformIO" I'd be
really annoyed that I have to rewrite all my client code because of what in
practice should be a local change to my implementation.
I'm saying that the Haskell types may describe too much detail about the
implementation in a way that is bad for modularity, because it prematurally
constrains the possible set of implementations. It is useful to be able to
say that a given implementation is pure in an interface. I'd personally
really like this feature in ML. However, when designing a modular and
resuable interface it's not clear that you should by "default" force all
implementations to be pure.
Paul Hudak
> It like saying look if I rewrite (1+2) as 4 my program
> is now different.
But if I rewrote 1+2 as 3 and that changed the meaning of my program,
that would bother me, and I'm arguing that my example falls into that
category. I think that it just depends on whose rules you are using --
i.e. normal beta vs. beta-value rule -- but I don't think that it's
right to say that something is bogus just because you're using a
different set of rules! We need to compare the complexity of the rules,
amongst other things. For example:
> The right way to rewrite the above is
>
> let fun x1 () = complexexpression1
> fun x2 () = complexexpression2
> in if pred then x1() else x2()
>
> This rewrite preserves the semantics, and is only just a little more
> syntactically clumsy than the previous one.
I move code around all of the time, and I like the freedom that lazy
evaluation gives me to do this without worrying about the above kind of
transformations. If I did what you suggest as a default every time I
moved code around, it would look ugly, and would violate my notion of
what abstraction and modularity are all about. Of course, I wouldn't
really do this: instead I would try to reason about the evaluation order
to avoid adding the "nullary argument" whenever possible. But the whole
point is that I don't have to do that reasoning when I use a lazy
language. This represents precisely the difference between the
complexities of reasoning about normal beta vs. beta-value.
> > (Designing a language with both evaluation mechanisms just
> > allows you to choose the poison many different times :-)
>
> Those of us who wish to commit suicide should be given a choice
> how we do it. :)
By the way, I should be clear here: I'm all in favor of a language that
allows such a choice! :-)
-Paul
Daniel C. Wang
Amr A Sabry <sa...@cs.uoregon.edu> writes:
{stuff deleted}
> I used to have the same criticism of Haskell (and ML's imperative
> type variables) but now I actually believe that it is the right thing to
> do to
> expose effects in the types of expressions.
>
> The issue goes beyond Haskell and ML. Consider how checked exceptions in
> Java must be made visible in the types of methods. I believe this was a
> good design decision, even though it does prevent you from replacing code
> that does not throw exceptions by code that might.
> One of the main lessons of monads is that if an expression may have
> effects then the type of the expression should reflect this. As you note:
> there is a cost to this additional precision. One can no longer naively
> interchange pieces of code that use different effects. But the general
> remedy is to develop mechanisms for "encapsulating effects" using
> technologies like type-and-effect systems.
I'm not going to disagree with the idea of making effects explicit in the
interface. It's quiet a useful thing, and I'd like to have it. The
question/challenge is how to do this in the "right way" that encourages
modularity and doesn't overly constrain implementations.
In particular rather than having interfaces describe what effects do
occur. It seems, better to describe in interfaces what effects don't occur.
By default one assumes the most general case of having all sorts of
effects. Therefore, an interfaces can be defined in such a way that by
default they admit for arbitrary effects, unless the interface designer
writes down an explicit grantee.
For example
val f : int -> int (* could do all sorts of ugly things *)
val g : (int -> int) no_unhandled_exceptions
val h : (int -> int) terminates
This approach, leads to better design, because by default interface
specifications are the most general and allow for the most implementation
freedom, so it's easier to mix code. This encourages people not to write
overly constrained interfaces. The current way monads are handled in
Haskell does it in the opposite way, and encourages people to write overly
restrictive interfaces.
Daniel C. Wang
Paul Hudak <paul....@yale.edu> writes:
{stuff deleted}
> Of course, I wouldn't
> really do this: instead I would try to reason about the evaluation order
> to avoid adding the "nullary argument" whenever possible. But the whole
> point is that I don't have to do that reasoning when I use a lazy
> language. This represents precisely the difference between the
> complexities of reasoning about normal beta vs. beta-value.
But this sort of reasoning is trivial* and at best avoids only some ugly
syntax, while reasoning about space usage and the semantics of nested
pattern matches is very non-trivial. Which is my point, the default lazy
semantics of Haskell at best makes trivial reasoning only slightly easier,
while it complicates many other things making them much harder when compared
to a strict language.
*Again for compilers this sort of thing really is trivial, just keep your
code in CPS form. It's only a bit little harder for your average
programmer.
{stuff deleted and out of context}
> I move code around all of the time, and I like the freedom that lazy
> evaluation gives me to do this without worrying about the above kind of
> transformations.
I think, we are also having a disagreement about what "abstraction and
modularity" are about. To me it's more about interfaces, data abstraction,
and modular code. Not about moving code around locally. It hard for me to
see how the Beta rule is some how better then the Beta-value rule with
respect to interface specification, data abstraction, and modular code.
Oh well... I should get back to that thesis..... :)
Nick Williams
Daniel C. Wang <danwan...@cs.princeton.edu> wrote:
>Here's a better example... I have a pure interface, and for
>debugging or profiling reasons, every time I call a function I
>want it to write an entry to a log file. In order to do this I
>have to use unsafePreformIO or muck with my interface and
>rewrite all my code that uses my pure interface, so that it
>uses a monadic interface. If I didn't have "unsafePreformIO"
>I'd be really annoyed that I have to rewrite all my client code
>because of what in practice should be a local change to my
>implementation.
One response to this would be that this is good sense: your
action of logging to the outside world is the generation of a
side-effect, your code is no longer pure...
Are you getting at the idea that purity is a subjective, rather
than objective, quality? It seems to me that in your above
example, what you're saying is that you _know_ that what you're
doing isn't notionally pure, but you'd like to regard it as pure
for reasons of expediency; i.e. so you don't have to rewrite
your client code to deal with a monadic type.
>I'm saying that the Haskell types may describe too much detail
>about the implementation in a way that is bad for modularity,
>because it prematurally constrains the possible set of
>implementations.
My view would be different: the Haskell type system (in the
context of monads) forces the programmer accurately to reflect
the fact that functions might be impure in their typing. Given
that most modern functional languages seem to have as their
premise that strong, safe typing systems are a virtue, this
seems to fit in with the pattern and to be consistent.
>It is useful to be able to say that a given implementation is
>pure in an interface. I'd personally really like this feature
>in ML. However, when designing a modular and resuable interface
>it's not clear that you should by "default" force all
>implementations to be pure.
This is not intended as a criticism of ML, or to spark a
language war, but I like the certainty I get from looking at a
Haskell function's type signature: I know at once whether the
interface to this function is pure or not. As you point out
above, lazy state threads mean that the internals of the
function may not be pure, but I can be certain that it will not
generate externally visible side-effects.
On the other hand, it is quite easy (and occasionally 'the
natural thing to do') to write functions in ML that appear (in
terms of their type signatures) to be pure, yet are not.
To my mind, having such information in the type system is a
positive benefit to modularity and reusability; not a hindrance.
From my perspective, a function is either pure, or impure, and
that assessment is performed objectively. I may be
misunderstanding, but you seem to be suggesting a sort of
'meta-typing' of functions, where a programmer can indicate
pureness. This seems to me a retrograde step, for the reasons
indicated above.
Nick Williams
Daniel C. Wang <danwan...@cs.princeton.edu> wrote:
I think initially the subject was modularity and clarity, rather
than abstraction, to be fair...
My understanding of Paul Hudak's point was not that interface
specification was made clearer by the use of a particular
reduction rule ahead of another, but that rather that lazy
semantics (and hence the Beta rule) give one less to worry about
when making changes to code: in a very real sense, lazy
semantics more accurately reflect the way that people thing and
that anything a language can do to remove the burden of
artificial thinking and mental gymnastics from the programmer
must be a good thing.
Of course, you make a fair point when you say that reasoning
about, (he says, attempting to get back to the subject) for
example, space usage is made more difficult.
The optimistic side of my mind says that full laziness, if
achievable, would be a good thing, and that the issues involved
in reasoning about space usage (the fact that 'correct' rewrites
can totally change the space-complexity of an algorithm, etc)
will be overcome, or worked around. Ditto for local worst-case
performance etc. :-)
Daniel C. Wang
> semantics more accurately reflect the way that people thing and
> that anything a language can do to remove the burden of
> artificial thinking and mental gymnastics from the programmer
> must be a good thing.
Not to sound like a troll, but do you really believe this?
Why do you think so many people get bitten by C macro bugs when mixed with
effects? I might believe a good mathematician thinks this way, but your
average C programer doesn't at all believe that
if (p) { return w++; } else { return w--; }
is the same as
int x1 = w++;
int x2 = w--;
if (p) { return x1; } else { return x2; }
Beta-value is the more natural rule for C, C++, Java, ML, Scheme, Lisp,
FORTRAN, Perl and gads of other programming lanuages. It's not at all hard
to reason with the Beta-value rule. I don't see any reason to believe that
the Beta rule seem more natural....
Daniel C. Wang
> language war, but I like the certainty I get from looking at a
> Haskell function's type signature: I know at once whether the
> interface to this function is pure or not. As you point out
> above, lazy state threads mean that the internals of the
> function may not be pure, but I can be certain that it will not
> generate externally visible side-effects.
I'm trying to make a subtle point and doing it very badly. It's not the
issue of being able to *read* an interface and understand what effects do or
do not happen. It's an issue of what effects should I allow when I write
down my interface in the first place.
For example there are several "Union-Find" algorithms which are completely
pure and then there is the variant that uses path-compression which is
impure. If I write down an interface for a generic Union-Find module, it
would be in my interest to choose the most general interface that allows for
effects so that the pure and impure implementations share a common interface
for all clients.
The programming style of Haskell however encourages me to write a pure
interface and pure programs, which in this case is too specific. I think,
this is a general problem. I'm grasping at straws a bit here, but this is a
non-trivial issue. It's the best way I can explain the gut feeling that
makes me cringe a little when I think about how purity interacts with real
programming.
Nick Williams
Daniel C. Wang <danwan...@cs.princeton.edu> wrote:
>> when making changes to code: in a very real sense, lazy
>> semantics more accurately reflect the way that people think and
>> that anything a language can do to remove the burden of
>> artificial thinking and mental gymnastics from the programmer
>> must be a good thing.
>Not to sound like a troll, but do you really believe this?
Yes: I do...
>Why do you think so many people get bitten by C macro bugs when
>mixed with effects? I might believe a good mathematician thinks
>this way, but your average C programer doesn't at all believe
>that
>
> if (p) { return w++; } else { return w--; }
>
>is the same as
>
> int x1 = w++;
> int x2 = w--;
> if (p) { return x1; } else { return x2; }
Well, I should hope not; they are obviously not the same,
_given_ the defined semantics of C.
This really isn't a useful comparison: C was always designed to
work this way: it's the principle of least-surprise at work for
a whole generation of programmers who have never been exposed to
lazy evaluation.
It may be natural to them, but it's probably much _less_ natural
to someone who's never been exposed to programming at all. I've
spent enough time trying to calculate loop invariants or reason
about pointer algorithms for really quite simple imperative
programs to think that this is not the way forward. Seeing as
how you're reading comp.lang.functional, you obviously feel
something like the same way.
Laziness is an innate human virtue: we generally try not to do
more than we need in order to come to a desired result. If the
people in the office say they need a printer, I don't go buy an
inkjet and a laser, and then give them whichever one they
finally decide they want.
By way of a contrived example, if I say:
"x is 39 and y is 57"
"let z be the value of x times twice the value of y"
"now tell me the value of x"
I'm betting that most people (apart from imperative programmers,
and those armed with calculators :-) ) don't bother to work out
that z is 4446.
Here's an example that isn't contrived: it's a section of a
Haskell program that does RSA public key algorithms; it does
fast modular exponentiation by addition chaining, calculating
x^y mod n:
> fastExp :: Integer -> Integer -> Integer -> Integer
> fastExp x y n
> | y == 1 = x `mod` n
> | y `mod` 2 == 0 = (a*a) `mod` n
> | otherwise = (c*x) `mod` n
> where a=fastExp x (y `div` 2) n
> b=fastExp x ((y-1) `div` 2) n
> c=(b*b) `mod` n
I'd argue this more accurately reflects the way that people
think about this problem than does the strict version.
Daniel C. Wang
ni...@thelonious.new.ox.ac.uk (Nick Williams) writes:
> In article <r8tya4h...@vista.cs.princeton.edu>,
{stuff deleted}
> > if (p) { return w++; } else { return w--; }
> >
> >is the same as
> >
> > int x1 = w++;
> > int x2 = w--;
> > if (p) { return x1; } else { return x2; }
>
> Well, I should hope not; they are obviously not the same,
> _given_ the defined semantics of C.
>
> This really isn't a useful comparison: C was always designed to
> work this way: it's the principle of least-surprise at work for
> a whole generation of programmers who have never been exposed to
> lazy evaluation.
>
> It may be natural to them, but it's probably much _less_ natural
> to someone who's never been exposed to programming at all. I've
{stuff deleted}
> Laziness is an innate human virtue: we generally try not to do
> more than we need in order to come to a desired result.
{stuff deleted}
This is a pretty bold claim about human nature. In any case my point is
simple, Beta vs. Beta-value is not that hard to teach or learn. It's not
obvious that either it "more natural" than the other. It is obvious, and it
seems everyone agrees that preserving the Beta rule in a programming
language makes lots of important operational reasoning difficult if not
impossible. Highly skilled Haskell programmers need space profilers to get
things right. While your first year C hacker can tell you the difference
between the two programs above. To me keeping the beta rule buys Haskell very
little and costs it a lot.
Tommy Thorn
saw was due to lazy evaluation or "something else".
"Daniel C. Wang" <danwan...@cs.princeton.edu> writes:
> Not to sound like a troll, but do you really believe this?
> Why do you think so many people get bitten by C macro bugs when mixed with
> effects? I might believe a good mathematician thinks this way, but your
> average C programer doesn't at all believe that
As your example shows, it is harder to read programs when you have to
take into account all the side-effects that might happend "behind your
back". This is especially the case when you might be reading code you
didn't write yourself.
As another case in point, ML compilers generally have to go to a great
deal of pain to detect which functions are pure and can be rearranged.
It seems straightforward for me. Purely functional non-strict
languages gives you a simpler denotational semantics which is good for
reasoning about programs and writing modular code. However the
operational semantics is more complex. This is a tradeoff, but I like
to get correctness first and efficiency later. IMHO, the advantage of
having effects explicit in the types outweigh the burden.
All that said, I'd like (better) support for strictness annotations.
Maybe in Haskell 2?
/Tommy
--
"Microsoft shouldn't be broken up. It should be shut down."
-- Security expert Bruce Schneier on the ILOVEYOU virus.
Bruce J. Bell
Nick Williams <ni...@thelonious.new.ox.ac.uk> wrote:
>In article <r8tbt1d...@vista.cs.princeton.edu>,
>Daniel C. Wang <danwan...@cs.princeton.edu> wrote:
[...]
>>It is useful to be able to say that a given implementation is
>>pure in an interface. I'd personally really like this feature
>>in ML. However, when designing a modular and resuable interface
>>it's not clear that you should by "default" force all
>>implementations to be pure.
>
>This is not intended as a criticism of ML, or to spark a
>language war, but I like the certainty I get from looking at a
>Haskell function's type signature: I know at once whether the
>interface to this function is pure or not. As you point out
>above, lazy state threads mean that the internals of the
>function may not be pure, but I can be certain that it will not
>generate externally visible side-effects.
How about this: on a machine with a finite amount of memory,
allocating space is not necessarily a "pure" operation either.
It reserves resources, and if they run out, you get the side-
effect of an out-of-memory error.
I realize computer languages are designed to mask the gory details
of memory management, and one of the big advantages of high-level
languages is that you don't have to deal with memory management
by hand like you do in C. But it seems like there should be some
way to express concerns resource use if you want to.
Any idea how?
Bruce
--
You are the lens of the world:
the lens through which the world may become aware of itself.
The world, on the other hand, is the only lens in which you can see yourself.
It is both lenses together that make vision. (--R. A. MacAvoy)
Albert Lai
Message-ID: <m34s73f...@career.localdomain>
Lines: 36
X-Newsreader: Gnus v5.6.45/XEmacs 21.1 - "Arches"
> By way of a contrived example, if I say:
>
> "x is 39 and y is 57"
> "let z be the value of x times twice the value of y"
> "now tell me the value of x"
>
> I'm betting that most people (apart from imperative programmers,
> and those armed with calculators :-) ) don't bother to work out
> that z is 4446.
I have to disagree here and agree with Daniel on this. Consider the
fairly well-known example:
Suppose you are a bus driver.
You start driving with the bus empty.
Then 6 passengers board at a stop.
Then at the next stop, 50% of the passengers leave..
Then at the next stop, some new passengers board, and the total
number increases by 20%.
Then at the next stop, 5 passengers with red shoes and 3 passengers
with black shoes board.
Then at the next stop, 1/3 of the passengers leave, and the number
of passengers with black shoes reduces to 1.
... more boarding and leaving ...
Question: what is the name of the bus driver?
You probably aren't tricked by this kind of thing, as you are used to
lazy evaluation and you just have the habit of looking at the question
first before you care about the given information. But most people
(me included) eagerly count the passengers and the shoes as they read
or listen.
--
[If you post a response, no need to cc me; if you cc me, please say so.]
Ancient number system: one, two, many.
Futuristic GUI number system: click, double-click, repeatedly click.
Ketil Z Malde
> I have to disagree here and agree with Daniel on this. Consider the
> fairly well-known example:
>
> Suppose you are a bus driver.
> You start driving with the bus empty.
> Then 6 passengers board at a stop.
[...]
> Question: what is the name of the bus driver?
> But most people (me included) eagerly count the passengers and the
> shoes as they read or listen.
Which is why you in Haskell have the "where" clause
What is the name of the bus driver where
the bus starts empty,
six passengers board
[...]
-kzm
--
If I haven't seen further, it is by standing in the footprints of giants
Marcin 'Qrczak' Kowalczyk
> How about this: on a machine with a finite amount of memory,
> allocating space is not necessarily a "pure" operation either.
> It reserves resources, and if they run out, you get the side-
> effect of an out-of-memory error.
IMHO the concept of purity is not 100% pure. There must be some
compromises when this is a real programming language, rather than
a mathematical model. Functions are pure only when talking about
them on a sufficiently high level of abstraction.
It's OK to be able to hide arbitrary I/O in a function looking as
pure when we are making an interface to a C function. Or to attach
a finalizer to be executed at any time when the object is garbage
collected. Sane library authors will not put bad things there,
100% safety is uncheckable by the compiler, and in effect we get
a convenient programming language with nice access to the C library.
It's OK to have unsafePerformIO, unsafeCoerce#, unsafeFreeze.
Programmers must be aware that when they use them, the responsibility
on basic correctness (even type correctness and validity of compiler
optimizations) is in their hands, not compiler's. They have a choice:
be safe or be able to do some tricks. It's impossible to have
everything and let the compiler check uncheckable, it's convenient
to be able to cheat.
Glasgow Haskell Compiler allows catching out of memory errors.
Catching is in IO, but errors are raised during evaluation of pure
expressions. I don't care much if it means that pure functions are in
fact not pure: I treat them as pure when I am making use of laziness,
I treat the larger part of a program as an imperative action when
I catch such errors, and I'm happy with this because it works and
is convenient.
Peter Hancock
>>>>> "Bruce" == Bruce J Bell <br...@krone.ugcs.caltech.edu> writes:
> I realize computer languages are designed to mask the gory details
> of memory management, and one of the big advantages of high-level
> languages is that you don't have to deal with memory management
> by hand like you do in C. But it seems like there should be some
> way to express concerns resource use if you want to.
> Any idea how?
This seems to be a very active and quite promising research area; one stream of it
is to develop "resource sensitive" type systems for programs. Many of the ideas
in this area stem from linear logic. Some names of people who work in this area
are
Martin Hofmann: http://www.dcs.ed.ac.uk/home/mxh/papers.html
helmut Schwichtenberg: http://www.mathematik.uni-muenchen.de/~schwicht
Jean-Yves Girard: http://iml.univ-mrs.fr/ftp/girard/
Daniel Leivant: http://www.cs.indiana.edu/people/l/leivant.html
Stephen Bellantoni: ??
Andreas Goerdt ??
Karl-Heinz Niggl: http://www.mathematik.uni-muenchen.de/~niggl/
I encourage you to have a look at what these people have been doing recently,
via their recent publications.
--
Peter
Marshall Abrams
wants to believe. I've done some functional programming in
Scheme and SML over the years, and know a little lambda calculus
and combinatorial logic. I currently have a job doing perl
programming in an object-oriented oriented company, and have
been around programmers, some quite intelligent, working in this
or that small organization, for years.
I've been using Haskell for a project at home. It's just a
beautiful langage. I love some of the higher-level constructs
it provides. Syntax has a lot to do with what I like about
Haskell. Laziness is slightly interesting, and allows some nice
(well, maybe only cute) techniques, like infinite lists, but
it's really not why I'm using Haskell. If SML code could look
like Haskell code can, I'd just as soon use that.
But IMHO, for almost all programmers working outside of
academia, the idea of doing without assignments would just seem
ludicrous. A lot of intelligent programmers don't even think of
making a function application the argument of another function.
i.e. I often come across code like this (in pseudocode):
foo (a, b, c) {
x = f(a, b, c);
y = g(x, 0);
z = h(y);
return z;
}
rather than
foo (a, b, c) {
return h(g(f(a, b, c), 0));
}
and I think people think the former is easier to read, actually,
because it's not as dense.
The guy I work for respects my opinions, and is intelligent and
open to learning new approaches. I may advocate functional
approaches to a certain extent. I think I can point out that
trying to figure out the side-effects in the code written by the
guy I replaced is the sort of thing that drives one crazy. Even
if you encapsulate the side-effects in an object, you still have
to figure out which state the object has at any given moment to
know how the code is going to behave at a given point in the
program.
But even if I decide that purely functional programming was
appropriate for where I work, and I could push the idea of doing
that, the idea of trying to convince people to deal with
laziness as well... it just seems laughable. It makes
something that every programmer understands--the evaluation of
function arguments--into something confusing. I just wouldn't
try to sell it. Getting people to do without loops in favor of
recursion is going to be hard enough.
And by the way, it seems to me that laziness gives Haskell,
despite its strict typing, one of the "features" that I have to
deal with in perl--at least in a limited way. That is, in
Haskell, there are contexts where it's easy for my code to have
a serious and simple bug which only manifests itself far from
its source, and my lay undetected for a long time: If I have an
unintended divizion by zero, I want to know it right away, not
when Haskell gets around to evaluating the expression--maybe.
--
Marshall Abrams ab...@midway.uchicago.edu
Basile STARYNKEVITCH
Please remove antispam device from my reply address (Basile S.)
>>>>> "Marshall" == Marshall Abrams <ab...@midway.uchicago.edu> writes:
Marshall> I'm not a lazy or even functional believer--call me
Marshall> someone who wants to believe. [...]
I don't know enough about Haskell, but I do know Ocaml...
Marshall> I've been using Haskell for a project at home. [...]
Marshall> But IMHO, for almost all programmers working outside of
Marshall> academia, the idea of doing without assignments would
Marshall> just seem ludicrous. A lot of intelligent programmers
Marshall> don't even think of making a function application the
Marshall> argument of another function. i.e. I often come across
Marshall> code like this (in pseudocode):
Marshall> foo (a, b, c) { x = f(a, b, c); y = g(x, 0); z = h(y);
Marshall> return z; }
Marshall> rather than
Marshall> foo (a, b, c) { return h(g(f(a, b, c), 0)); }
Marshall> and I think people think the former is easier to read,
Marshall> actually, because it's not as dense.
In Ocaml (and SML) one can write either
let foo a b c = h (g (f a b c) 0) ;;
which matchs the first heavy style or
let foo a b c =
let x = f a b c in
let y = g x 0 in
let z = h y in
z
;;
which matches the second style.
In otherwords, functional style is not "programming without
assignments" but rather more "programming without *OVERWRITING*
assignment"; most assignment (even in C) are logically single (ie the
variable -at least in the programmer's head- is assigned exactly
once). A single assignment is exactly a let ... in ... construct.
Regards
NB. please remove antispam device from my reply address.
--
Basile STARYNKEVITCH - 8 rue de la Faiencerie, 92340 BOURG LA REINE (France)
tel 01.46.65.45.53. email = basile point starynkevitch at wanadoo point fr
http://perso.wanadoo.fr/starynkevitch/basile
antispam: <ab...@wanadoo.fr>
Albert Lai
Message-ID: <m3k8fn6...@career.localdomain>
Lines: 19
X-Newsreader: Gnus v5.6.45/XEmacs 21.1 - "Arches"
> I think many programmers agree that functional
> programming is pretty, but it is *hard* to use Haskell for most of the
> things that C++ commonly gets used for. Hard enough that you could
> probably write a masters thesis about most of them. (I'm not kidding;
> there have been papers on writing fifteen year old Nintendo games in
> Clean and doing simple animation in Haskell.)
The same can be said about structured programming when it was about
ten to twenty years old. I imagine that assembly and goto programmers
were saying "there are papers on simply creating and traversing linked
lists with abstract pointers and while-loops, but I have been doing
this in Fortran with gotos and arrays, and my friend have been doing
this in assembly --- both without the bloat of a heap manager!"
Otherwise I mostly agree with your points and suggestions.
--
[If you post a response, no need to cc me; if you cc me, please say so.]
No brain, no life.
Tommy Thorn
...
> I've been using Haskell for a project at home. It's just a
> beautiful langage. I love some of the higher-level constructs
> it provides. Syntax has a lot to do with what I like about
> Haskell. Laziness is slightly interesting, and allows some nice
> (well, maybe only cute) techniques, like infinite lists, but
> it's really not why I'm using Haskell. If SML code could look
> like Haskell code can, I'd just as soon use that.
It can't. When I was introduced to Haskell, I was thinking much the
same as you. I soon realised that the syntax and semantics are
strongly related and just made me like Haskell even more.
One of the major points about non-strictness and pure is that you can
lift expressions (modulo free variables) out of their context, ie.
f = let a = e1 in
let b = e2 in
in c = e3 a in
\x y -> e4
is the _same_ (modulo free variables) as
f x y = let
c = e3 a
b = e2
a = e1
in
e4
or even better
f x y = e4 where a = e1; b = e2; c = e3 a
In a strict and/or non-pure language that wouldn't be the case as
expressions e1, e2, and e3 may have side effects or even fail to
terminate. In Haskell "side effects" are explicit in the type and are
generally implemented with a monad, such as the IO monad, so you can
easily distinguish pure expressions from non-pure. For someone coming
from an imperative world this might be really annoying at first, but
IMHO you can learn to appreciate it very much for all the benefits it
brings.
These days, rather than have SML with Haskell syntax (and types!), I'd
much rather have Haskell with better support for manual strictness
annotations.
/Tommy
George Russell
[snip]
> i.e. I often come across code like this (in pseudocode):
>
> foo (a, b, c) {
> x = f(a, b, c);
> y = g(x, 0);
> z = h(y);
> }
>
> rather than
>
> foo (a, b, c) {
> return h(g(f(a, b, c), 0));
> }
functions, since it makes immediately clear what order they will be executed
in. Perhaps if programmers could trust functions to be really non-side-
effecting, they will come to prefer the second style?
Hartmann Schaffer
the second version makes it as clear (how do you, in a strict
language, evaluate a function without first evaluating its arguments.
even in a lazy language f is completed before g before h.
--
Hartmann Schaffer
George Russell
> the second version makes it as clear
we had h(g(f(a,b,c),k(d,e))) instead then I think
compiler would be entitled to call f and k in either
order. Or perhaps concurrently? (I don't know.)
Hannah Schroeter
In article <r8tbt1d...@vista.CS.Princeton.EDU>,
Daniel C. Wang <danwan...@cs.princeton.edu> wrote:
>qrc...@knm.org.pl (Marcin 'Qrczak' Kowalczyk) writes:
>[...]
>I just took a peek at the lazy state thread work. It doesn't solve all of
>the problem. Lazy state threads let me run a stateful computation and then
>use it's result in a pure setting.
>But consider
>type Map a
>insert :: Map a -> a -> Map a
>What I'm complaining about is simply the fact the type of insert gurantees
>me that it has "no-side observable effects". Even if I used the ST monad
>and lazy state threads internally this property is preserved. (Which is
>quiet cool...)
Right.
>However for Splay trees I must have an interface of the form
>insert :: ST (Map a) -> a -> ST (Map a)
No. It'd be
insert :: DestructiveMap a -> a -> ST ()
(you want to do it in place)
>because the splay trees must use side effects and the effect *must be
>observerable outside* of insert in order to get the amortized performance
>neccessary.
Okay. Then the signature Map a -> a -> Map a is just *wrong*,
because that signature guarantees that if you
let m0 = some creation of a Map a
m1 = insert m0 a
in expr
you can use BOTH m0 and m1 randomly in expr. With destructive updates,
that's just not possible, so that guarantee would be violated.
If you want to do impure programming, do it in an appropriate state
monad, such as:
newDMap :: ST (DMap a)
insertDMap :: DMap a -> a -> ST ()
deleteDMap :: DMap a -> a -> ST Bool -- was the element found or not?
lookupDMap :: DMap a -> a -> ST Bool
...
>Here's a better example... I have a pure interface, and for debugging or
>profiling reasons, every time I call a function I want it to write an entry
>to a log file. In order to do this I have to use unsafePreformIO or muck
>with my interface and rewrite all my code that uses my pure interface, so
>that it uses a monadic interface. If I didn't have "unsafePreformIO" I'd be
>really annoyed that I have to rewrite all my client code because of what in
>practice should be a local change to my implementation.
Use trace or unsafePerformIO. That's one of the legitimations for
those language extensions.
>I'm saying that the Haskell types may describe too much detail about the
>implementation in a way that is bad for modularity, because it prematurally
>constrains the possible set of implementations. It is useful to be able to
>say that a given implementation is pure in an interface. I'd personally
>really like this feature in ML. However, when designing a modular and
>resuable interface it's not clear that you should by "default" force all
>implementations to be pure.
As above, the user of a module sees the signature
Map a -> a -> Map a
and is entitled to assume that the user can use both the first argument and
the result whenever she likes.
You can of course change the interface to *always* read like the impure
one, even if the implementation is pure.
Or have two interfaces, a pure one, and an impure one (e.g. as
two type classes). Pure implementations can provide both, impure ones
only the impure one. The user decides which of both interfaces she needs.
Regards, Hannah.