Có thể sử dụng lệnh gọi/cc để thực hiện đệ quy không?

Question

Tôi tự hỏi liệu có thể định nghĩa một hàm đệ quy mà không cần gọi hàm đó trong cơ thể của nó nhưng bằng cách nào đó sử dụng lệnh gọi/cc thay thế? Cảm ơn.

Answer 1

Bạn có thể triển khai bộ kết hợp Y bằng cách sử dụng call/cc, as described here. (! Rất cám ơn đến John Cowan đề cập đến bài gọn gàng này) Trích dẫn bài đó, đây là thực hiện Oleg của:

luỵ 1. Y Combinator qua call/cc - Y Combinator mà không có một tự ứng dụng rõ ràng.

(define (Y f) 
    ((lambda (u) (u (lambda (x) (lambda (n) ((f (u x)) n))))) 
    (call/cc (call/cc (lambda (x) x))))) 

Ở đây, chúng tôi sử dụng một thực tế là

((lambda (u) (u p)) (call/cc call/cc)) 

và

((lambda (u) (u p)) (lambda (x) (x x))) 

là observationally tương đương.

Answer 2

Câu hỏi của bạn hơi mơ hồ. Đặc biệt, có vẻ như bạn muốn một hệ thống mô hình các cuộc gọi đệ quy mà không trực tiếp thực hiện các cuộc gọi đệ quy, sử dụng lệnh gọi/cc. Mặc dù vậy, hóa ra bạn có thể lập mô hình các cuộc gọi đệ quy mà không thực hiện các cuộc gọi đệ quy và cũng mà không cần sử dụng lệnh gọi/cc. Ví dụ:

#lang racket 

(define (factorial f n) 
    (if (= n 0) 1 (* n (f f (- n 1))))) 

(factorial factorial 3) 

Điều đó có vẻ như gian lận, nhưng đó là nền tảng của bộ kết hợp Y. Có lẽ bạn có thể thắt chặt các hạn chế mà bạn đang nghĩ đến?

P.S .: nếu đây là bài tập về nhà, hãy trích dẫn tôi!

Answer 3

Tôi sợ call/cc không thực sự liên quan nhiều đến điều này. Thực sự chỉ có hai cách xác định hàm đệ quy:

• Giả sử ngôn ngữ của bạn cho phép định nghĩa hàm đệ quy; tức là, một cơ quan chức năng có thể tham chiếu đến hàm kèm theo, hoặc phần thân của hàm f có thể tham chiếu đến hàm g có thân thể đề cập đến f. Trong trường hợp này, tốt, bạn chỉ cần viết nó theo cách thông thường.
• Nếu ngôn ngữ của bạn cấm cả hai, nhưng nó vẫn có chức năng hạng nhất và lambdas, thì bạn có thể sử dụng fixed-point combinator như bộ kết hợp Y. Bạn viết hàm của bạn để nó lấy làm đối số thừa một hàm có nghĩa là đại diện cho bước đệ quy; mọi nơi bạn sẽ tái chế, thay vào đó bạn gọi lập luận đó.

Vì vậy, đối factorial, bạn viết nó như thế này:

(define (factorial-step recurse n) 
    (if (zero? n) 
     1 
     (* n (recurse (- n 1))))) 

Sự kỳ diệu của combinator Y là nó xây dựng các recurse chức năng đó sẽ được làm thức ăn cho factorial-step.