3

在 Little Schemer 的第 9 章中，作者介绍了以下两个函数

(define Q 
  (lambda (str n) 
    (cond 
      ((zero? (remainder (first$ str ) n)) 
        (Q (second$ str ) n)) 
      (t (build (first$ str ) 
        (lambda ( ) 
          (Q (second$ str ) n))))))) 

(define P
  (lambda (str)
    (build (first$ str)(lambda () (P (Q str (first$ str)))))))

并建议通过以下执行对它们进行评估：

(frontier (P (second$ (second$ int)))  10)

你会如何在 Common Lisp 中编写 P 和 Q 函数？

（我自己翻译了 Y-Combinator - 但我发现这个很有挑战性）

--辅助功能--

(define frontier
  (lambda (str n)
    (cond
      ((zero? n) (quote ()))
        (t (cons (first$ str) (frontier (second$ str) (sub1 n)))))))

(define str-maker
  (lambda (next n)
    (build n (lambda () (str-maker next (next n))))))

(define int (str-maker add1 0))

(define second$
  (lambda (str)
    ((second str))))

(define first$ first)

(define build
  (lambda (a1 a2)
    (cond
      (t (cons a1
        (cons a2 (quote ())))))))))

(define first
  (lambda (p)
    (cond
       (t (car p)))))

(define second
  (lambda (p)
    (cond
      (t (car (cdr p))))))

(define add1 
  (lambda (n)
    (+ 1 n)))

(define remainder 
  (lambda  (n m)
    (cond
      (t (- n (* m (/ n m ))))))

（免责声明 - 这不是家庭作业问题 - 这是为了我的理解和学习）

4

1 回答 1

6

我以为：

  • 在 P 定义中，“(Q (str (first$ str)))”的意思是：“(Q str (first$ str))”，因为 Q 是一个有两个参数的函数。
  • build是一个帮助器，它确实创建了 first$ 和 second$ 工作的东西：列表

考虑到这一点，将 Scheme 直接翻译成 Common Lisp 会给出：

(defun first$ (list) (first list))
(defun second$ (list) (funcall (second list)))
(defun build (a b) (list a b))

(defun frontier (str n)
  (if (zerop N)
    ()
    (cons (first$ str) (frontier (second$ str) (1- n)))))

(defun str-maker (next n)
  (list n (lambda () (str-maker next (funcall next n)))))

(setq int-maker (str-maker #'1+ 0))

(defun Q (str n)
  (if (zerop (rem (first$ str) n))
    (Q (second$ str) n)
    (list (first$ str) (lambda () (Q (second$ str) n)))))

(defun P (str)
  (list (first$ str) (lambda () (P (Q str (first$ str))))))

(frontier (P (second$ (second$ int-maker))) 10)

最后一行返回：

(2 3 5 7 11 13 17 19 23 29)

这是一个众所周知的系列，所以我认为翻译是成功的:-)

于 2009-11-13T17:21:28.187 回答