🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.lang.functional
Article #915

Re: Is efficient backtracking feasible in functional languages?

#915
From: Julian Seward (DRL PhD)
Date: Fri, 13 Nov 1992 09:54
27 lines
1872 bytes
Kevin Hammond writes:

| The Haskell B. (and LML) implementations have (or had) some
| interesting space leaks (as Dave Wakeling's profiler pointed out).
| One of these was due to not "black-holing" closures when they were
| entered (so retaining space if arguments to the original closure
| became dead before the closure was fully evaluated).  It sounds as if
| this may be the problem reported with the Haskell B implementation.
| The most recent implementation has compiler flags to fix the problems
| which Dave Wakeling reported, but I think they're disabled by default
| (black-holing costs time, for instance, which you may not want to
| spend).

I thought the 0.998.* versions of lml/hbc have blackholing
*on* by default.  Anyway, you can turn it on manually
by issuing the flag -fzap-redex to lml or hbc.

I suspect blackholing doesn't cost more than about 5% in performance
terms, but it would be interesting for someone to quantify this.
As I understand it, the Glasgow compiler maintains a stack of
pointers to closures under evaluation, so the garbage collector
can do the redex zapping, rather than impose that cost on the
mutator.  lml/hbc unfortunately has to zap every closure as it
goes along, which is more expensive.

Jules
Technical Details
Message-ID: <SEWARDJ.92Nov13095450@r6a.cs.man.ac.uk>
Path: arc1-ca.pugleaf.net!sparky!uunet!mcsun!uknet!mucs!m1!sewardj
References: <TMB.92Nov12122350@arolla.idiap.ch> <1992Nov12.162725.25836@cs.yale.edu> <BxM80r.1Hu@dcs.glasgow.ac.uk>

Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!mcsun!uknet!mucs!m1!sewardj
From: sewardj@cs.man.ac.uk (Julian Seward (DRL PhD))
Newsgroups: comp.lang.functional
Subject: Re: Is efficient backtracking feasible in functional languages?
Message-ID: <SEWARDJ.92Nov13095450@r6a.cs.man.ac.uk>
Date: 13 Nov 92 09:54:50 GMT
References: <TMB.92Nov12122350@arolla.idiap.ch> <1992Nov12.162725.25836@cs.yale.edu>
 <BxM80r.1Hu@dcs.glasgow.ac.uk>
Sender: newsman@cs.man.ac.uk
Organization: Department of Computer Science, University of Manchester
Lines: 27
In-reply-to: kh@dcs.glasgow.ac.uk's message of 12 Nov 92 18:14:49 GMT