Article View: comp.lang.functional
Article #919Re: Is efficient backtracking feasible in functional languages?
From: Lennart Augustsson
Date: Tue, 17 Nov 1992 04:20
Date: Tue, 17 Nov 1992 04:20
20 lines
1761 bytes
1761 bytes
The Haskell program ss n = head [ x | x<-[0..], x>n ] does indeed use linear space with hbc 0.998.5. The reason for this is that all Prelude functions (in this case head) are compiled without overwriting the root redex. If you define your own head function the program runs in constant space (416 bytes to be exact). The reason for not overwriting the root redex has nothing todo with efficiency consideration; "zapping" the redex only takes about 3% longer. The reason is that I wanted the Prelude functions to work with the interactive system. Zapping (blackholing) does not work well with the interactive system because here you can interrupt computation with ^C (admittedly not entirely clean), and the graph should be in a consistent state if you do. Having black holes around makes it inconsistent (or at least unusable). I hope to have the Prelude compiled with zapping in the next release. -- -- Lennart Augustsson [This signature is intentionally left blank.]
Technical Details
Message-ID:
<1992Nov17.042026.19290@cs.chalmers.se>Path:
arc1-ca.pugleaf.net!sparky!uunet!charon.amdahl.com!pacbell.com!decwrl!sun-barr!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!math.fu-berlin.de!mailgzrz.TU-Berlin.DE!cs.tu-berlin.de!news.netmbx.de!Germany.EU.net!mcsun!sunic!chalmers.se!cs.chalmers.se!augustssReferences:
<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!charon.amdahl.com!pacbell.com!decwrl!sun-barr!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!math.fu-berlin.de!mailgzrz.TU-Berlin.DE!cs.tu-berlin.de!news.netmbx.de!Germany.EU.net!mcsun!sunic!chalmers.se!cs.chalmers.se!augustss From: augustss@cs.chalmers.se (Lennart Augustsson) Newsgroups: comp.lang.functional Subject: Re: Is efficient backtracking feasible in functional languages? Keywords: lazy backtracking Gofern Message-ID: <1992Nov17.042026.19290@cs.chalmers.se> Date: 17 Nov 92 04:20:26 GMT References: <TMB.92Nov12122350@arolla.idiap.ch> <1992Nov12.162725.25836@cs.yale.edu> <BxM80r.1Hu@dcs.glasgow.ac.uk> Sender: news@cs.chalmers.se (News administrator) Organization: Chalmers University of Technology Lines: 20