home *** CD-ROM | disk | FTP | other *** search
- Path: sparky!uunet!snorkelwacker.mit.edu!ai-lab!life.ai.mit.edu!tmb
- From: tmb@arolla.idiap.ch (Thomas M. Breuel)
- Newsgroups: comp.lang.functional
- Subject: Re: Is efficient backtracking feasible in functional languages?
- Date: 12 Nov 92 12:23:50
- Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
- Perceptive)
- Lines: 62
- Message-ID: <TMB.92Nov12122350@arolla.idiap.ch>
- References: <1992Nov11.171742.18783@eua.ericsson.se> <lg3071INN8m1@exodus.Eng.Sun.COM>
- Reply-To: tmb@idiap.ch
- NNTP-Posting-Host: arolla.idiap.ch
- In-reply-to: staffan@chivas.Eng.Sun.COM's message of 11 Nov 92 21:53:37 GMT
-
- Someone wrote:
-
- anon> strangesucc n = hd [x|x<-[0..];x>n];
- anon> [this runs out of memory and uses space linear in n]
-
- I replied that there is no reason why this should use space linear in n:
-
- tmb> - Stream.head(Stream.filter(fn x => x > 1000000,Stream.iota()));
- tmb>
- tmb> [Major collection... 21% used (3397260/15733684), 1920 msec]
- tmb>
- tmb> [Major collection... 21% used (3397288/15730836), 1910 msec]
- tmb>
- tmb> [Major collection... 21% used (3397288/15730948), 1920 msec]
- tmb>
- tmb> [Major collection... 21% used (3397288/15730888), 1920 msec]
- tmb>
- tmb> [Major collection... 21% used (3397288/15730888), 1910 msec]
- tmb> val it = 1000001 : int
- tmb> -
-
- In article 18783@eua.ericsson.se, joe@erix.ericsson.se (Joe Armstrong) writes:
- joe>
- joe> Wonderfull !!
- joe>
- joe> This is the kind of stuff that gives FP a bad name :-)
-
- It only gives "FP a bad name" if you intepret this naively. The
- performance of the SML implementation that I gave is actually quite
- good: unlike the Haskell version that the other person referred to, it
- uses only constant space. And, in my experience, memory management
- overhead is significantly less than for similar code in CommonLisp or
- C++.
-
- Note also that the GC was deliberately configured to run frequently in
- this example so that you can see how much memory is actually used at
- various points during the computation.
-
- joe> Is their a transformation system which can prove that
- joe> strangesucc x == x + 1 ?
-
- In article <lg3071INN8m1@exodus.Eng.Sun.COM> staffan@chivas.Eng.Sun.COM (Staffan Liljegren) writes:
- staffan> So it's not only SML that has these problems. So what are
- staffan> some better mechanisms for representing backtracking OR how
- staffan> can You circumvent this problem ?
-
- Let's nip this rumor in the bud: SML has no problem with this
- construct. Streams are a lazy data structures, and you pay a certain
- price for that. Yes, the compiler might be able to figure out in some
- cases that it optimize away this loop, but I certainly don't expect it
- to in more complex cases.
-
- In general, in a lazy language, you are often at the mercy of the
- compiler to prove things about your code in order to obtain decent
- performance. Fortunately, in SML, you have better control over
- resources than in a lazy language, so if the Stream data structures
- are too inefficient for your purposes (which is actually only rarely
- the case), you can choose alternative constructs based on callcc or
- tail recursion instead and be more certain about what resource
- requirements your program will actually have.
-
- Thomas.
-