Scheme: Lazy evaluation

stateless · 06-14-2013, 12:30 PM

Hi. I'm learning scheme, having some background in Haskell. For keyboard exercise, I create a fibonacci (helper) function like so:

Code:

guile> (define fib_ (lambda (a b n) (if (< n 2) (cons a '()) (cons a (fib_ b (+ a b) (- n 1))))))
guile> (fib_ 1 1 10)
(1 1 2 3 5 8 13 21 34 55)

Elegant, recursive. But if I try to do a large number of sequences (>600) guile crashes with stack overflow. Presumably, due to strict evaluation.

I know there is delay and force (procedures?) but I am having difficulty understanding them and properly applying them here. I would appreciate any guidance or explanations that might be helpful.

ntubski · 06-15-2013, 02:13 AM

Quote:

But if I try to do a large number of sequences (>600) guile crashes with stack overflow.

With guile-2.0 it throws a vm-error instead of outright crashing, and it happens at 8105 instead of 600.

Quote:

Presumably, due to strict evaluation.

From a typical scheme perspective this is due to a lack of tail recursion. The naive recursive version has call depth n. The tail recursive version has call depth 1. I think Haskell doesn't maintain a call stack separate from the heap, so it can't have stack overflow.

Code:

(define fib-tr
  (lambda (a b n list)
    (if (< n 1)
        (reverse! list)
        (fib-tr b (+ a b) (- n 1) (cons a list)))))
;;;
scheme@(guile-user)> (fib-tr 1 1 10 '())
$1 = (1 1 2 3 5 8 13 21 34 55)

Quote:

I know there is delay and force (procedures?)

delay is a macro (it has to be since it uses a non-standard evaluation order), and force is a procedure.

You can use delay to return a promise of a list (of any expression, in fact). However, the builtin display functions don't give a useful output:

Code:

(define fib-lazy
  (lambda (a b n)
    (if (< n 2)
        (delay (cons a '()))
        (delay (cons a (fib-lazy b (+ a b) (- n 1)))))))
;;;
scheme@(guile-user)> (fib-lazy 1 1 10)
$2 = #<promise #<procedure 29c2060 at <current input>:14:8 ()>>

You can use force to extract the value from a promise, this can be used to create a function that prints the first n values from a promise of a list:

Code:

(define (print-promised-list promised-list n)
  (let* ((list (force promised-list))
         (head (car list))
         (tail (cdr list)))
    (display head)
    (display " ")
    (cond
     ((null? tail)
      (display "\n"))
     ((> n 1)
      (print-promised-list tail (- n 1)))
     (else (display "...\n")))))
;;;
scheme@(guile-user)> (print-promised-list $2 3)
1 1 2 ...
scheme@(guile-user)> (print-promised-list $2 10)
1 1 2 3 5 8 13 21 34 55

To handle longer lists you'll probably want to implement something like Haskell's drop.

EDIT: Instead of implementing this from scratch, SRFI 41 "Streams" provides many useful functions for creating and manipulating lazy lists.

hydraMax · 06-15-2013, 10:28 AM

Thanks, very helpful answer.

stateless · 06-18-2013, 12:17 PM

May I ask you a little bit more about this: Do schemers usually try hard to make their recursive functions tail-recursive, or do they just ignore the stack overflow issue? (Or turn off stack limits in production systems...?)

The scheme documentation/tutorial I'm using advertises the recursive function (base case + recursive case) as the ideal, but it doesn't mention the stack overflow issue. I found that making my functions tail-recursive is usually not difficult, but usually the tail-recursive version is a little bit less natural looking and forces the involvement of some extra operation. (Like the reverse! in your above example.)

sundialsvcs · 06-18-2013, 01:57 PM

Quote:

Originally Posted by stateless

May I ask you a little bit more about this: Do schemers usually try hard to make their recursive functions tail-recursive, or do they just ignore the stack overflow issue? (Or turn off stack limits in production systems...?)

The scheme documentation/tutorial I'm using advertises the recursive function (base case + recursive case) as the ideal, but it doesn't mention the stack overflow issue. I found that making my functions tail-recursive is usually not difficult, but usually the tail-recursive version is a little bit less natural looking and forces the involvement of some extra operation. (Like the reverse! in your above example.)

As it turns out, most "recursive" algorithms that you are likely to encounter are tail-recursive. They are "conveniently defined in terms of themselves," which makes them "recursive," yet they usually don't do something that requires a recursive call to be completed before a final answer for the current iteration can be produced. (Therefore, there's really no reason to maintain n entries on a call-stack: the only thing we're going to do at that point is to get rid of it, so why do we have it.) Tail-recursive versions do look a little bit "stilted," but they are nonetheless worth creating.

ntubski · 06-18-2013, 08:33 PM

Quote:

Originally Posted by stateless

May I ask you a little bit more about this: Do schemers usually try hard to make their recursive functions tail-recursive, or do they just ignore the stack overflow issue? (Or turn off stack limits in production systems...?)

I don't actually use scheme to build real programs myself, but my impression is that tail-recursive functions are strongly preferred. Higher order functions (map, fold) can often abstract away the difference.

Quote:

The scheme documentation/tutorial I'm using advertises the recursive function (base case + recursive case) as the ideal, but it doesn't mention the stack overflow issue.

Perhaps it's introduced later? I would be surprised if it doesn't come up at all.

Quote:

I found that making my functions tail-recursive is usually not difficult, but usually the tail-recursive version is a little bit less natural looking and forces the involvement of some extra operation. (Like the reverse! in your above example.)

The tail recursive version usually needs an extra "accumulator" parameter which in some sense is equivalent to a mutable variable in an imperative version of the algorithm. Functions which build a list have the extra reverse annoyance because the cons functions forces you to build the list backwards. If you had a function that appends instead of prepending there wouldn't be a need to reverse (unfortunately, such a function would require mutation so it would not mesh with a functional style).