[plt-scheme] Lazy evaluation and tail calls

  ----- Original Message ----- 
  From: James Coglan 
  To: Eli Barzilay 
  Cc: PLT Scheme ML 
  Sent: Sunday, January 18, 2009 4:07 PM
  Subject: Re: [plt-scheme] Lazy evaluation and tail calls





  2009/1/18 Eli Barzilay <eli at barzilay.org>

    On Jan 17, James Coglan wrote:
    >
    > Right now, I've got a very bare bones Scheme and I'm more interested
    > in algorithms for optimising stuff rather than tools in a specific
    > language.


    The `lazy' promises that Jos mentioned are not just tools: they are
    essentially a way to implement delayed evaluation in a way that is
    still safe for space.  You describe how your evaluator is holding an
    expression with the appropriate bindings -- and this is essentially a
    promise value.  The promises that are implemented in PLT's
    scheme/promise library are therefore very relevant, and a solution (to
    some degree) to your problem is what that code is doing.


  Sorry for the misunderstanding: I just meant to emphasise that I was more after a language-neutral discussion of algorithms for the problem I was trying to solve. I imagine at some point I will want to implement delay/force in my Scheme, but for now I want a way to make Scheme transparently lazy. This is mostly because I'm reading "To Mock a Mockingbird" and doing some lambda calculus, which requires normal order evaluation in order to be directly expressed in Scheme.


  Joe, Jos: sadly I'm not equipped to provide any formal reasoning at this stage -- Scheme and SICP are really my first foray into any formal study of computer science. All I can tell is that it looks like you'd need to somehow evaluate the promises from the inside out iteratively and have the result propagate into the binding of the next outer promise before evaluating it, so you'd be able to evaluate the promises in the some order as you would in call-by-value. This would involve every promise storing references to any promises that need its value, which would use extra storage space, and you'd need to flatten the tree of promise dependencies without using recursion in the host language. I'll let you know if I figure something out.
Exactly, you are on the right track, I think. As I earlier wrote in a private email, you should, I think, first find out about self lifting promises as referred to by Eli (and very well and very generally implemented in PLT (Thanks Eli)). Then, there is a way to transform a tail recursive procedure into a space safe reference to an element of a stream. An interesting idea, thanks. In fact PLT's lazy scheme (thanks again Eli) does that (or at least comes very close)

Using lazy Scheme, you can write a laymans implementation of `equal-fringe?' and have it operate without any superfluous generation of the parts of the fringes that are not relevant. That is the inequality should be detected before the remainder of the two fringes have been formed that follow two inequal elements. Just an example, but a good one, I think.

Another nice example of how laziness can go wrong is described in SRFI 40 (by Phil Bewig). It is called the times3 problem. It has been adequately been solved in srfi 45 (Andre van Tonder) and used in srfi 41 (Phil Bewig)
Jos




------------------------------------------------------------------------------


  _________________________________________________
    For list-related administrative tasks:
    http://list.cs.brown.edu/mailman/listinfo/plt-scheme
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090118/95fa94c7/attachment.html>