headers
Richard Uhtenwoldt | 1 Dec 2002 05:53
Picon

RE: Running out of memory in a simple monad

David Bergman writes:

>It is easy to get the feeling that the recursive call in
>
>	recurse = do
>	   		f x
>         		recurse
>
>is the last one, but this is just an illusion of the iterative layout of
>"do". Sometimes the monads lure us into old iterative thought
>patterns...
>
>Taking away the syntactic sugar, we end up with
>
>	recurse = f x >> recurse
>
>This reveals the fact that there can be no last call optimization,
>because the last call is ">>".

What do you mean by this?  Do you mean that that an implementation
cannot execute arbitrarily many iterations/recursions of that last
loop/definition in constant space?

If that's what you mean, you are wrong.  GHC does that.  The IO monad
would be pretty damned useless for actual work if implementations did
not do that!

Even if we replace the (>>) with a (:) as the "main operator"/"last
call" of the loop, the result can execute in constant space because
of optimizations.
(Continue reading)

Permalink | Reply | 7 comments |
headers
David Bergman | 1 Dec 2002 08:23
Picon
Favicon

RE: Running out of memory in a simple monad

Richard,

I assumed that the compiler had, through strictness analysis, used a
call stack in the compiled code, instead of the usual call frames in the
heap (equivalent to "hey, I thought this was the Standard ML mail
group?") ;-)

Actually, you are right in that the "last call optimization" is not
vital in most call-by-need scenarios, since both (the implicit) call
stack and data structures are often consumed as generated, and the GC
can reclaim the thunks. Note: In an unoptimized scenario, such as with
Hugs, you do indeed run out of memory in your "loop" (after some 40000
iterations) not having the recursion in the last call. Even loops not
constructing cons cells do, such as

	loop 0 = return ()
	loop n = do { print n; loop (n-1) } -- print n >> loop (n-1)
	main = loop 50000

(you see Hugs die after some 25000 iterations...)

Sorry about the over-simplification, but I wanted people to not forget
that the "do" is just syntactic sugar...

Thanks,

David

-----Original Message-----
From: Richard Uhtenwoldt
(Continue reading)

Permalink | Reply | 3 comments |
headers
David Bergman | 1 Dec 2002 19:12
Picon
Favicon

RE: Running out of memory in a simple monad

So,

Should I imply that the IO monad is "pretty damned useless" in Hugs
then, since the loop does not run in constant space there?

There are a lot of algorithms that cannot be run in constant space (due
to either recursion depth or structure generation), even in the most
optimized setting. This does not make them useless.

/David

-----Original Message-----
From: haskell-admin <at> haskell.org [mailto:haskell-admin <at> haskell.org] On
Behalf Of Richard Uhtenwoldt
Sent: Saturday, November 30, 2002 11:53 PM
To: David Bergman
Cc: haskell <at> haskell.org
Subject: RE: Running out of memory in a simple monad

David Bergman writes:

>It is easy to get the feeling that the recursive call in
>
>	recurse = do
>	   		f x
>         		recurse
>
>is the last one, but this is just an illusion of the iterative layout
of
>"do". Sometimes the monads lure us into old iterative thought
(Continue reading)

Permalink | Reply | 2 comments |
headers
Richard Uhtenwoldt | 1 Dec 2002 21:37
Picon

The Haskell 98 Report

Simon PJ writes:

>                     the existing notice that says "you can do what
>you like with this Report" will stay unchanged.  No "non-commercial
>only" caveats.

I remained relatively quiet throughout the discussion,
as I have not contributed to the Report, but I'm very
much relieved.

Scheme, too, has a completely free standards document; we do
not want to give up ground to them :)

Thank you, Simon.
Permalink | Reply | 0 comments |
headers
Richard Uhtenwoldt | 1 Dec 2002 23:47
Picon

RE: Running out of memory in a simple monad

David Bergman writes:

>Should I imply that the IO monad is "pretty damned useless" in Hugs
>then, since the loop does not run in constant space there?

my statement was too broad.  allow me to amend it.

some are using Haskell for "systems programming", as a better C
than C.  some, including me, would like to see more of that,
with Haskell or another pure functional language with an IO monad
taking systems programmers away from the C and C++ communities.

Hugs is completely useless for *that*.

for an example of Haskell as a better C than C, see Chak's Gtk+
bindings.  to use them you must write your whole GUI in the IO monad
in a style where the basic data structures and control structures
closely resemble what you would write in C.

see
http://www.cse.unsw.edu.au/~chak/haskell/gtk/BoolEd.html
and note how most of the functions are in the IO monad.

many Haskellers have a negative opinion of such heavy use of the
IO monad, but in systems programming you need more control over
when (relative to other interactions) your program performs an
interaction with a file, network or UI resource than is available
in Haskell without the IO monad.

--
(Continue reading)

Permalink | Reply | 1 comment |
headers
David Bergman | 2 Dec 2002 00:27
Picon
Favicon

Carried away in the monads? was: RE: Running out of memory in a simple monad

Richard wrote:

> some are using Haskell for "systems programming", as a better C
> than C.  some, including me, would like to see more of that,
> with Haskell or another pure functional language with an IO monad
> taking systems programmers away from the C and C++ communities.

That is good, I would probably call myself a C++ developer primarily,
but Haskell + the IO monad is a much better choice (even better than
Perl...) in most situations.

> Hugs is completely useless for *that*.

Yes, it is, although it is great for testing the validity of one's
Haskell programs.

> for an example of Haskell as a better C than C, see Chak's Gtk+
> bindings.  to use them you must write your whole GUI in the IO monad
> in a style where the basic data structures and control structures
> closely resemble what you would write in C.

I have seen it, and it is a bit imperative in its style.

> many Haskellers have a negative opinion of such heavy use of the
> IO monad, but in systems programming you need more control over
> when (relative to other interactions) your program performs an
> interaction with a file, network or UI resource than is available
> in Haskell without the IO monad.

I must confess that I belong to that "theoretical" group, although I am
(Continue reading)

Permalink | Reply | 0 comments |
headers
Andrew J Bromage | 2 Dec 2002 00:37
Favicon
Gravatar

Re: AW: slide: useful function?

G'day all.

On Thu, Nov 28, 2002 at 12:32:19PM -0500, Paul Hudak wrote:

> reminds of what I think is one of the biggest problems with conventional
> software development: the lack of appreciable mathematics in the
> specification, design, coding, or implementation of programs.

In the interest of fairness, the declarative programming community
occasionally appears to have an aversion to actual engineering.  If
you mention a term like "design patterns", people look down their
virtual noses at you like you're trying to infect their pure
theoretical world with something unsanitary.

My point is that nobody is immune from this kind of thinking, it
just takes different forms.

Cheers,
Andrew Bromage
Permalink | Reply | 14 comments |
headers
Johannes Waldmann | 2 Dec 2002 08:26
Picon

Re: AW: slide: useful function?

On Mon, 2 Dec 2002, Andrew J Bromage wrote:

> ... If you mention a term like "design patterns", 

well I love design patterns, it's just that in Haskell-land 
they are called higher-order functions, or polymorphic functions, etc.

I think you need  `design pattern' as a special concept
only if you can't express it in the language itself
(that is, if all your functions are first order,
if you can't write polymorphic code, 
or can't typecheck it properly, etc.)
as it happens for most of the mainstream languages ...
--

-- 
-- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --
-- joe <at> informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/207 --
Permalink | Reply | 10 comments |
headers
William Lee Irwin III | 2 Dec 2002 09:01

Re: AW: slide: useful function?

On Mon, Dec 02, 2002 at 10:37:09AM +1100, Andrew J Bromage wrote:
> In the interest of fairness, the declarative programming community
> occasionally appears to have an aversion to actual engineering.  If
> you mention a term like "design patterns", people look down their
> virtual noses at you like you're trying to infect their pure
> theoretical world with something unsanitary.
> My point is that nobody is immune from this kind of thinking, it
> just takes different forms.

I've got some issues here:

(1) Various things I'm doing as a practitioner lack theoretical
	background (and/or content) for various problems in them.
	e.g. how does one measure per-cpu time spent waiting on io on SMP?
	e.g. page replacement mixes kinds of memory, creating list searches
(2) In theory and in practice I've seen "design patterns" and a couple
	other "popular" programming movements add up to nothing. Design
	patterns in particular produced precisely zero useful code or
	code design during its entire lifetime as designs on the level on
	which its principles operate are not ever getting freshly redone.
(3) Various tidbits of theoretically motivated languages assume so much
	infrastructure as to be unsuitable for various (kernel)
	environments. There's a circular dependency between what some
	things implement and the infrastructure assumed, which is where
	the problem lies.
(4) There is no excuse for willful ignorance. Linear searches in
	interrupt context and other gross inefficiencies have brought
	systems down because the events triggering the poor algorithms
	occurred in realtime and are generated by hardware. They
	consistently livelocked boxen with sufficient cpu counts.
(Continue reading)

Permalink | Reply | 2 comments |
headers
John Hughes | 2 Dec 2002 10:27
Picon
Picon

Re: AW: slide: useful function?

> On Mon, 2 Dec 2002, Andrew J Bromage wrote:
>
> > ... If you mention a term like "design patterns",
>
> well I love design patterns, it's just that in Haskell-land
> they are called higher-order functions, or polymorphic functions, etc.
>
> -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --

Or maybe more general notions, such as

   "define a recursive datatype together with a catamorphism combinator"

or even

   "embed a domain-specific language via combinators over an ADT"

There are patterns of that sort in our programs, which we would probably
rather call design techniques, which aren't so easily captured by a
higher-order function definition.

John
Permalink | Reply | 4 comments |

Gmane