Sieve of Eratosthenes in Scheme using mutation of local state in its filtering procedure

Question

While answering a recent question I came up with the following code, implementing a variant of the sieve of Eratosthenes, repeatedly culling the initial 2...n sequence, stopping as early as possible:

(define (sieve2 n)
  (let ((ls (makelist n)))
    (let loop ((ls ls) 
               (next (sievehelper2 ls n)))
      (if (null? next)
          ls
          (cons (car ls) 
                (loop next (sievehelper2 ls n)))))))

(define (sievehelper2 list n)
  (if (> (* (car list) (car list)) n)
      '()
      (filterfunc (not-divisible-by (car list)) 
                  list)))

(define filterfunc filter)

(define (not-divisible-by n)
  (let ((m n))   ; the current multiple of n
    (lambda (x)
      (let ((ret (not (= x m))))
        (if (>= x m) (set! m (+ m n)) #f)
        ret))))

(define (makelist n)
  (range 2 (+ 1 n)))

Running (sieve 50) in Racket results in '(2 3 3 5 5 7 7 11 11 13 17 19 23 29 31 37 41 43 47) though.

It has some error in it, as is obvious in the results, and I don't immediately see where it is. It can either be some stupid mistake that I made or an expression of some fundamental misalignment of the algorithmic pieces in use, and I can't say which is which.

What is that error and how can it be fixed, please?

To be clear, I'm not asking for algorithmic improvements to the code, I want the computational structure expressed in it preserved. Moreover, the challenge that I saw in the linked question was to devise the missing functions -- and alter the sieve itself -- while keeping the sievehelper function as given, up to some minor alterations as evident in this question's code. This is also a requirement I'd like to make in this question.

I'm also not happy with the two calls to sievehelper2 in sieve2. Perhaps fixing the code structure somehow will also make the error go away?

Answer 1

The problem is here:

(loop next (sievehelper2 ls n))

The list ls is passed for a second time to sievehelper2 in this call; but sievehelper2 needs to process next:

(define (sieve2 n)
  (let ((ls (makelist n)))
    (let loop ((ls ls) 
               (next (sievehelper2 ls n)))
      (if (null? next)
          ls
          (cons (car ls) 
                (loop next (sievehelper2 next n)))))))

With this change, the sieve seems to work as expected:

sieve2.rkt> (sieve2 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)

It may help code clarity to get rid of the outer let in sieve2, and make only one call to sievehelper2:

(define (sieve3 n)
  (let loop ((filtered '())
             (candidates (makelist n)))
    (if (null? candidates)
        filtered
        (cons (car candidates) 
              (loop (cdr candidates) (sievehelper2 candidates n))))))

This also works as expected:

sieve2.rkt> (sieve3 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)

---

Some Improvements

I am not happy with sieve3 above. While I think that showing only one call to sievehelper2 aids clarity, the code could still be made more clear.

Initially sieve3 had a result variable which has since been changed to filtered. result was not descriptive enough to be helpful, and I think that the change is an improvement; after all, filtered does contain the results of filtering the candidates list. Although, the initial value of filtered is meaningless in that sense because candidates has not yet been filtered.

What bothers me more is the construction:

(cons (car candidates) 
      (loop (cdr candidates) (sievehelper2 candidates n)))

It is not very clear that (car candidates) is a prime that is being collected and that (cdr candidates) is the partially filtered list of candidates, or that the goal is to cons primes which have been found onto a fully filtered list of candidates.

Here is an improved version of sieve that uses an explicit accumulator primes to save prime numbers as they are encountered. When sievehelper2 returns an empty list, we know that the filtered list has been fully filtered of non-prime numbers. Finally, the found primes and the fully filtered list of candidates can be appended together and returned (but not before reversing the list of found primes, since the most recently found primes are consed onto the front of primes). This sieve procedure also has the virtue of being tail-recursive:

(define (sieve n)
  (let loop ((primes '())
             (filtered (makelist n)))
    (let ((next (sievehelper2 filtered n)))
      (if (null? next)
          (append (reverse primes) filtered)
          (loop (cons (car filtered) primes)
                next)))))

sieve2.rkt> (sieve 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)

Answer 2

update: After some mulling over I've come to dislike the new structure and re-appreciate the one I came up with originally.

It comes from the perspective of working with a pair -- the current sequence, and its next iteration (with the error fixed, thanks to the answer by ad absurdum):

(define (sieve2_fixed n)
  (let ((start (makelist n)))
    (let loop ((this               start   ) 
               (next (sievehelper2 start n)))
      (if (null? next)
          this
          (cons (car this) 
                (loop               next
                      (sievehelper2 next n)))))))

the original (deprecated) answer follows, just for the record.

---

Thanks to the answer from ad-absurdum, the error is now fixed.

As to the code error issue, what I should have done really was to use proper names for the variables in the first place, like so:

(define (sieve2a n)
  (let ((start (makelist n)))
    (let loop ((this start) 
               (next (sievehelper2 start n)))
      (if (null? next)
          this
          (cons (car this) 
                (loop next         ;____ error: `this`: WRONG
                      (sievehelper2 this n)))))))

The only thing changed here compared to sieve2 in the question are the names (and one more newline). Now the error is clear, and chances are with these names it could be much easier for me to notice it myself.

As to the code structure and clarity issue, I'm not too fond of the build-in-reverse paradigm used in the sieve re-write from that answer. Yes it is a staple of functional programming, but actually, it doesn't have to be anymore -- not if we run our code in Racket, where the heap is used for the stack, stack overflow is as impossible as total memory exhaustion, and the straight tail-recursive-modulo-cons code just might have better performance, having avoided the superfluous reverse.

Now looking at the fixed version, putting the this and the next together as the loop variables was misguided, done in an attempt to avoid another, inner let for some reason. But the computation is much clearer expressed with it, as

(define (sieve2b n)
  (let loop ((this (makelist n))) 
     (let ((next (sievehelper2 this n)))
        (if (null? next)
          this
          (cons (car this)
                (loop next))))))

;; Start with the range of numbers. On each iteration,
;; try running the helper to get the next version of the list. 
;; If the attempt produces '(), stop and use what we've got
;;   as the remaining prime numbers, which they all are.
;; Otherwise, keep the first number as the next prime, and go on 
;; using that "next" version in the next iteration of the loop.

Now there's only one call to helper as it should be, the code is clear, and the original error becomes impossible to make just as I had hoped / suspected.

Simplicity and straightforwardness wins over unnecessary overcomplification. D'oh.