How to use of laziness in Scheme efficiently?-CodePudding

I am trying to encode a small lambda calculus with algebraic datatypes in Scheme. I want it to use lazy evaluation, for which I tried to use the primitives delay and force. However, this has a large negative impact on the performance of evaluation: the execution time on a small test case goes up by a factor of 20x.

While I did not expect laziness to speed up this particular test case, I did not expect a huge slowdown either. My question is thus: What is causing this huge overhead with lazy evaluation, and how can I avoid this problem while still getting lazy evaluation? I would already be happy to get within 2x the execution time of the strict version, but faster is of course always better.

Below are the strict and lazy versions of the test case I used. The test deals with natural numbers in unary notation: it constructs a sequence of 2^24 sucs followed by a zero and then destructs the result again. The lazy version was constructed from the strict version by adding delay and force in appropriate places, and adding let-bindings to avoid forcing an argument more than once. (I also tried a version where zero and suc were strict but other functions were lazy, but this was even slower than the fully lazy version so I omitted it here.)

I compiled both programs using compile-file in Chez Scheme 9.5 and executed the resulting .so files with petite --program. Execution time (user only) for the strict version was 0.578s, while the lazy version takes 11,891s, which is almost exactly 20x slower.

Strict version

(define zero    'zero)
(define (suc x) (cons 'suc x))

(define one   (suc zero))
(define two   (suc one))
(define three (suc two))

(define (twice m)
  (if (eq? m zero)
      zero
      (suc (suc (twice (cdr m))))))

(define (pow2 m)
  (if (eq? m zero)
      one
      (twice (pow2 (cdr m)))))

(define (consume m)
  (if (eq? m zero)
      zero
      (consume (cdr m))))

(consume (pow2 (twice (twice (twice three)))))

Lazy version

(define zero    (delay 'zero))
(define (suc x) (delay (cons 'suc x)))

(define one   (suc zero))
(define two   (suc one))
(define three (suc two))

(define (twice m)
  (delay
    (let ((mv (force m)))
      (if (eq? mv 'zero)
          (force zero)
          (force (suc (suc (twice (cdr mv)))))))))

(define (pow2 m)
  (delay
    (let ((mv (force m)))
      (if (eq? mv 'zero)
          (force one)
          (force (twice (pow2 (cdr mv))))))))

(define (consume m)
  (delay
    (let ((mv (force m)))
      (if (eq? mv 'zero)
          (force zero)
          (force (consume (cdr mv)))))))

(force (consume (pow2 (twice (twice (twice three))))))

CodePudding user response：

This sounds very like a problem that crops up in Haskell from time to time. The problem is one of garbage collection.

There are two ways that this can go. Firstly, the lazy list can be consumed as it is used, so that the amount of memory consumed is limited. Or, secondly, the lazy list can be evaluated in a way that it remains in memory all of the time, with one end of the list pinned in place because it is still being used - the garbage collector objects to this and spends a lot of time trying to deal with this situation.

Haskell can be as fast as C, but requires the calculation to be strict for this to be possible.

I don't entirely understand the code, but it appears to be recursively creating a longer and longer list, which is then evaluated. Do you have the tools to measure the amount of memory that the garbage collector is having to deal with, and how much time the garbage collector runs for?

CodePudding user response：

What you are trying to do is not encode a small lambda calculus with algebraic datatypes but you try to encode the Peano arithmetics, which is the first step up to "a small lambda".

I tried to write you some code that does it in a "faster way". Because I do not use the special forms force and delay in my code I used instead thunks to encode their logic.

(define succ
  (lambda (x)
    (lambda ()
      (cons 'succ x))))

(define zero (lambda () 'zero))
(define one (succ zero))
(define two (succ one))
(define three (succ two))

(define twice
  (lambda (n)
    (define twice
      (lambda (k)
        (if (eq? 'zero k)
          n
          (succ (twice ((cdr k)))))))
    (twice (n))))

(define pow2
  (lambda (n)
    (if (eq? 'zero n)
      one
      (twice (pow2 ((cdr n)))))))

(define print10
  (lambda (n)
    (define toten
      (lambda (n)
        (if (eq? n 'zero)
          0
          (  1 (toten ((cdr n)))))))
    (display (toten (n)))
    (newline))))

(print10 zero)
(print10 one)
(print10 two)
(print10 three)
(print10 (twice three))
(print10 (pow2 (zero)))
(print10 (pow2 (one)))
(print10 (pow2 (two)))
(print10 (pow2 (three)))

A test session should look so:

% mit-scheme --silent <peano.scm
0
1
2
3
6
1
2
4
8