Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!unmvax!pprg.unm.edu!hc!lll-winken!uunet!mcvax!ukc!etive!lfcs!jha
From: jha@lfcs.ed.ac.uk (Jamie Andrews)
Newsgroups: comp.lang.prolog
Subject: infinite structures, lazy evaluation
Message-ID: <1770@etive.ed.ac.uk>
Date: 14 Apr 89 10:29:54 GMT
References: <1632@kulcs.kulcs.uucp> <1942@randvax.UUCP> <1353@murtoa.cs.mu.oz.au> <1944@randvax.UUCP> <986@quintus.UUCP>
Sender: news@etive.ed.ac.uk
Reply-To: jha@lfcs.ed.ac.uk (Jamie Andrews)
Organization: Laboratory for the Foundations of Computer Science, Edinburgh U
Lines: 27


     I agree with Richard that you can still "prove theorems"
about infinite lazily evaluated data structures, contrary to
what Sanjai has claimed.  The only real problem is defining what
an infinite list is, which is a problem both in the logical and
the functional case.  Colmerauer and others have developed
pretty good semantics for infinite lists, though.

     However, I would agree with Sanjai that it's easier, or
more elegant, to do lazy evaluation in functional languages.
This seems to be because there's only one place where the value
of a variable can flow from -- the evaluation of a function call
-- so it can be delayed in the form of the function call.  With
logic programming, it's not always obvious where the value is
going to come from, which of course is the whole point of LP.

     Without true functions, we have to rely on clause
re-ordering, coroutining, very smart evaluators, and so on to
get the effect of lazy evaluation.  With functional programs,
it can be done fairly neatly.

     Old remarks about programmers' difficulties in following
lazy evaluation still apply, though...

--Jamie.
  jha@lfcs.ed.ac.uk
"Mayan skies sleeptalk with voices of lovers"