🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.lang.functional
Article #919

Re: Is efficient backtracking feasible in functional languages?

#919
From: Lennart Augustsson
Date: Tue, 17 Nov 1992 04:20
20 lines
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!augustss
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!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