[plt-scheme] Lazy evaluation and tail calls

From: Jos Koot (jos.koot at telefonica.net)
Date: Sat Jan 17 10:50:39 EST 2009

There is an important difference between normal order and lazy order. But let's assume you really mean lazy order. In that case you need to use syntax `lazy', not `delay' (see srfi 45, immediately available in PLT's scheme/base) When using delay, you may easily create deeply nested promises. For example, when you implement promises simply as:

(define-syntax delay (syntax-rules () ((_ x) (lambda () x))))
(define (force x) (x))

you are going to have problems. You need a more subtle type of promises (those like srfi 45)

In normal order ((lambda (x) (cons x x)) (begin (write 'foo) 'foo)) writes `foo' twice, in lazy order once only. You might check for that. If you implemented normal order rather than lazy order, the problem does not surprise me. You may also want to look into srfi 41 (streams) which implements and shows many examples of lazy order evaluation.

I have two implementations that allow mixing lazy and eager evaluation, but I am not yet satisfied about them and therefore do not yet want to present them to this list. If you are interested, let me know. Last but not least, did you look in the lazy scheme of PLT? Very instructive.
Jos
  ----- Original Message ----- 
  From: James Coglan 
  To: PLT Scheme ML 
  Sent: Saturday, January 17, 2009 3:42 PM
  Subject: [plt-scheme] Lazy evaluation and tail calls


  Hi there,

  My apologies if this is the wrong place to be asking this, but I'm new to Scheme and am not sure where I can get this question answered. If you know a better place to ask this, please point me in the right direction.

  Basically, I'm learning Scheme by implementing it in Ruby while reading SICP. I've added tail calls and also an optional lazy (normal-order) evaluation mode, but I can't get the two to play together. I have a factorial function that runs iteratively in eager mode, but it blows up the stack in lazy mode.

  I was wondering whether it's possible to have tail call optimisation when using normal order. I don't want to bang my head against the wall trying to make it happen if it can't be done.

  -- 
  James Coglan



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


  _________________________________________________
    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/20090117/facc269c/attachment.html>

Posted on the users mailing list.