生成素数时“应用程序：不是程序”

Question

我正在尝试输出前 100 个素数并不断收到错误消息：

应用程序：不是程序；期望一个可以应用于给定参数的过程：(#) arguments...：[none]

错误显示在我的 take$ 程序中：

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

这是我所有的代码：

(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)))))

感谢您的任何帮助，您可以提供。

Answer 1

您的问题是您使用抽象 Sieve 的方式不一致。

是这样定义的筛子：

;; 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

或者是这样定义的

;; 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

在代码中的某个地方，你是提取P和调用它像这样： ((cdr st)); 在其他地方，像这样：((cadr st))

对您的问题的评论者对每个人都表示怀疑的原因是，您没有对形成筛子和从筛子中提取子部分的规则给出一个高级定义。像上面这样的数据定义会对此有所帮助。

对我来说，在我添加数据定义、合同，然后开始单独测试您的功能后，我很快就发现了问题。（提示：这与上面提到的((cdr st))和之间的不一致有关((cadr st))。）

这是我的代码版本。它通过将 Sieve 表示的选择隐藏在抽象接口后面来本地化它；我使用了一个宏来执行此操作，因为流构造函数想要延迟对其接收的表达式的评估（尽管可以通过更改接口来解决此问题，因此 Sieve 构造函数需要采用生成筛子的过程而不是直接表达式） .

读者练习：使用当前的api，如果有人遵循我在此代码中给出的数据定义，stream-empty?则永远不会返回true；你怎么能证明这一点？

;; 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))))