Opened 4 years ago

Closed 3 years ago

Last modified 8 months ago

#4219 closed bug (wontfix)

sequence is not tail recursive, doesn't work with large inputs in strict monads

Reported by: EyalLotem Owned by:
Priority: normal Milestone: 7.2.1
Component: Compiler Version: 6.12.3
Keywords: sequence tail recursive Cc: daniel.is.fischer@…, cheecheeo@…
Operating System: Unknown/Multiple Architecture: x86
Type of failure: None/Unknown Difficulty: Unknown
Test Case: Blocked By:
Blocking: Related Tickets:

Description

replicateM 10000000 (randomIO >>= evaluate)

blows the stack because of "sequence".

I think it is important for Haskell programmers to be able to compose existing components without having to worry about the operational semantics of laziness, so it is important for GHC to specialize "sequence" calls to a tail-recursive one when a strict monad is in use.

Attached is the test case.

Attachments (1)

TestRandomIO.hs (147 bytes) - added by EyalLotem 4 years ago.

Download all attachments as: .zip

Change History (9)

Changed 4 years ago by EyalLotem

comment:1 Changed 4 years ago by igloo

  • Milestone set to 6.14.1

comment:2 Changed 4 years ago by daniel.is.fischer

  • Cc daniel.is.fischer@… added

comment:3 Changed 3 years ago by igloo

  • Milestone changed from 7.0.1 to 7.0.2

comment:4 Changed 3 years ago by cheecheeo

  • Cc cheecheeo@… added

comment:5 Changed 3 years ago by simonpj

What do you expect to happen here? You are asking GHC to build a big list. (Yes, it is then discarded, but the loop that produces the list doesn't know that.) How can we produce a big list? Something like this:

loop :: Int -> IO [Int]
loop 0 = return []
loop n = do { r <- randomIO; rs <- loop (n-1); return (r:rs) }

But that is obviously not tail recursive. Maybe you want this?

loop :: Int -> IO [Int]
loop n = do { rs <- tr_loop n []; return (reverse rs) }
  where
    tr_loop 0 rs = rs
    tr_loop n rs = do { r <- randomIO; tr_loop (n-1) (r:rs)

Doing that automatically would be hard, esp as you'd want to be sure that cost of the extra reverse was justified. Oh... the numbers are random so you don't need to reverse it. But do you expect the compiler to know that?

In short, I'm dubious that there's a simple, general optimsation that we are missing. I'd love to know one -- please show me.

comment:6 Changed 3 years ago by igloo

  • Milestone changed from 7.0.2 to 7.2.1

comment:7 Changed 3 years ago by igloo

  • Resolution set to wontfix
  • Status changed from new to closed

We don't have a general way to optimise this, so closing.

comment:8 Changed 8 months ago by nh2

  • Difficulty set to Unknown

Another way to treat this is to make the stack size unbounded by default.

As far as understand, this is now more feasible than it was when this bug was opened.

This way, the user would not have problems with the operational semantics as originally asked for.

(By the way, while in this bug the problem is seen as something hard to optimize, you could also understand using the stack for lists as an optimization that breaks things.)

I opened http://ghc.haskell.org/trac/ghc/ticket/8189 to discuss the issue.

Note: See TracTickets for help on using tickets.