"application: not a procedure" while generating prime numbers

Question

I am trying to output the first 100 prime numbers and keep getting the error:

application: not a procedure; expected a procedure that can be applied to arguments given: (#) arguments...: [none]

The error is shown in my take$ procedure here:

(if (or (= m 0) (null? st))
      '()
      (cons (car st) (take$ (- m 1) ((cdr st)))))))

Here it all my code:

(define int-builder$
    (lambda (x)
       (list x (lambda () (int-builder$ (+ 1 x ))))))

(define take$
    (lambda (m st)
       (if (or (= m 0) (null? st))
           '()
           (cons (car st) (take$ (- m 1) ((cdr st)))))))

(define filter-out-mults$
   (lambda (num  st)
     (cond
     (( = (remainder (car st) num) 0) 
         (filter-out-mults$ num ((cadr st))))
         (else 
            (list (car st) (lambda () (filter-out-mults$ num ((cadr st)))))))))

(define sieve$
   (lambda (st)
     (list (car st)
          (lambda() (sieve$ (filter-out-mults$ (car st) ((cadr st))))))))

(define stol$
    (lambda (n) 
      (take$ n (sieve$ (int-builder$ 2)))))

Thanks for any help you can provide.

Answer 1

Your problem is that you have not been consistent in how you have been using your abstract Sieve.

Is a sieve defined like this:

;; A Sieve is a (cons n p), where
;;    n is a Natural Number
;;    p is a Procedure that takes no arguments and returns a Sieve

or is it defined like this

;; A Sieve is a (list n p), where
;;    n is a Natural Number
;;    p is a Procedure that takes no arguments and returns a Sieve

In some places in your code, you are extracting the p and invoking it like this: ((cdr st)); in other places, like this: ((cadr st))

The reason that the commenters on your question were looking askance at each of those individually is that you have not given a high-level definition for what the rules are for forming Sieves and extracting subparts from Sieves. A data definition like the one above would help this.

For me, after I added data-definitions, contracts, and then started testing your functions individually, I quickly found the problem. (Hint: It has something to do with the inconsistency between ((cdr st)) and ((cadr st)) noted above.)

Here is my version of your code. It localizes the choice of Sieve representation by hiding it behind an abstract interface; I used a macro to do this since the stream constructor wants to delay evaluation of the expression it receives (though one could work around this by changing the interface so the Sieve constructor was required to take a sieve-producing procedure rather than a direct expression).

Exercise for reader: With the current api, and if someone follows the data definition I have given in this code, stream-empty? can never return true; how could you prove this?

;; A Stream is a (list Nat (-> () Stream))
;; but this knowledge should not be used anywhere but in the
;; procedures (and special form) stream-rest, stream-first, stream,
;; and stream-empty?.

;; stream-rest: Stream -> Stream
(define (stream-rest st) ((cadr st)))

;; stream-first: Stream -> Nat
(define (stream-first st) (car st))

;; Special Form: (stream <natural-number> <stream-expr>) is a Stream
(define-syntax stream
  (syntax-rules ()
    ((stream n expr) (list n (lambda () expr)))))

;; Stream -> Boolean
(define (stream-empty? st) (null? st))


;; Nat -> Stream
(define (int-builder$ x)
  (stream x (int-builder$ (+ 1 x))))

;; Nat Stream -> [Listof Nat]
(define (take$ m st)
  (if (or (= m 0) (stream-empty? st))
      '()
      (cons (stream-first st) (take$ (- m 1) (stream-rest st)))))

;; Nat Stream -> Stream
(define (filter-out-mults$ num st)
  (cond
   (( = (remainder (stream-first st) num) 0)
    (filter-out-mults$ num (stream-rest st)))
   (else 
    (stream (stream-first st) (filter-out-mults$ num (stream-rest st))))))

;; Stream -> Stream
(define (sieve$ st)
  (stream (stream-first st)
          (sieve$ (filter-out-mults$ (stream-first st) (stream-rest st)))))

;; Nat -> [Listof Nat]
(define (stol$ n)
  (take$ n (sieve$ (int-builder$ 2))))