Làm thế nào để chuyển đổi tính toán CPS kiểu gcd sử dụng Tiếp tục Monad

Question

Chúng ta hãy xem xét việc thực hiện sau đây của đơn nguyên Tiếp tục, cho phép tính CPS-phong cách năng suất và số nguyên:

module Cont : sig 
    type 'a t = ('a -> int) -> int 
    val return : 'a -> 'a t 
    val bind : 'a t -> ('a -> 'b t) -> 'b t 
    val callCC: (('a -> 'b t) -> 'a t) -> 'a t 
end = struct 
    type 'a t = ('a -> int) -> int 

    let return x = 
    fun cont -> cont x 

    let bind m f = 
    fun cont -> m (fun x -> (f x) cont) 

    let callCC k = 
    fun cont -> k (fun x -> (fun _ -> cont x)) cont 
end 

Làm thế nào chúng ta có thể viết lại CPS- thực hiện phong cách tính toán gcd (xem How to memoize recursive functions?) và đặc biệt là việc ghi nhớ để tận dụng lợi thế của Cont monad?

Sau khi xác định

let gcd_cont k (a,b) = 
    let (q, r) = (a/b, a mod b) in 
    if r = 0 then Cont.return b else k (b,r) 

Tôi cố gắng để sử dụng các loại giải để cho tôi gợi về loại rằng chức năng memoization nên có:

# let gcd memo ((a,b):int * int) = 
    Cont.callCC (memo gcd_cont (a,b)) (fun x -> x) 
;; 
    val gcd : 
    (((int * int -> int Cont.t) -> int * int -> int Cont.t) -> 
    int * int -> (int -> 'a Cont.t) -> int Cont.t) -> 
    int * int -> int = <fun> 

Tuy nhiên tôi không thể quay gợi ý này thành một thực hiện thực tế. Có ai đó có thể làm điều này không? Logic đằng sau việc sử dụng "callCC" trong chức năng ghi nhớ là nếu một giá trị được tìm thấy trong bộ đệm, thì đây là điều kiện thoát sớm.

Answer 1

Tôi cảm thấy vấn đề là trong câu trả lời của mình cho How to memoize recursive functions?, Michael gọi là phong cách CPS không phải là kiểu CPS. Trong kiểu CPS, đối số tiếp tục bổ sung k được sử dụng bất cứ khi nào một người muốn trả về một giá trị - giá trị sau đó được áp dụng cho k thay thế.

Đây không phải là thực sự những gì chúng ta muốn ở đây, chứ không phải những gì thực hiện:

let gcd_cont k (a,b) = 
    let (q, r) = (a/b, a mod b) in 
    if r = 0 then b else k (b,r) 

Ở đây, k không được sử dụng cho trở về (b được trả trực tiếp), nó được sử dụng thay vì thực hiện một cuộc gọi đệ quy. Thao tác này sẽ rút lại sự đệ quy: trong phạm vi gcd_cont, người ta có thể nghĩ về k là gcd_cont chính nó, giống như nếu let rec được sử dụng. Sau đó, gcd_cont thể được biến thành một chức năng thực sự đệ quy sử dụng một combinator fixpoint, mà về cơ bản "feeds nó để bản thân":

let rec fix f x = f (fix f) x 
let gcd = fix gcd_cont 

(đây là tương đương với call hàm Michael định nghĩa)

Các sự khác biệt với việc xác định gcd trực tiếp bằng cách sử dụng let rec là phiên bản có đệ quy được bung ra cho phép một "công cụ" các cuộc gọi đệ quy, vì bản thân đệ quy được thực hiện bởi bộ kết hợp điểm cố định. Đây là những gì chúng tôi muốn ghi nhớ: chúng tôi chỉ muốn thực hiện đệ quy nếu kết quả không có trong bộ nhớ cache. Vì vậy, định nghĩa của một tổ hợp memo.

Nếu chức năng được xác định bằng let rec, đệ quy sẽ được đóng cùng lúc với việc xác định hàm, do đó người ta không thể đưa ra các trang gọi đệ quy để chèn ghi nhớ. Là một lưu ý phụ, hai câu trả lời về cơ bản thực hiện cùng một điều: sự khác biệt duy nhất là cách chúng thực hiện đệ quy trong bộ kết hợp điểm cố định: tổ hợp điểm sửa chữa của Michael sử dụng let rec, Jackson sử dụng một tham chiếu, nghĩa là "nút của Landin" - một cách khác để thực hiện đệ quy, nếu bạn có tài liệu tham khảo bằng ngôn ngữ của bạn.

Sooo, để kết luận, tôi muốn nói thực hiện điều đó trong đơn nguyên tiếp tục không thực sự có thể/không thực sự có ý nghĩa, vì điều này không phải là CPS ngay từ đầu.