Sử dụng Tiếp để có được giá trị từ tương lai và quá khứ

Question

Tôi đang viết một thông dịch viên Brainfuck trong Haskell, và tôi đã đưa ra những gì tôi tin là một mô tả rất thú vị của chương trình:

data Program m = Instruction (m()) (Program m) 
       | Control (m (Program m)) 
       | Halt 

Tuy nhiên , thật khó để phân tích một biểu diễn văn bản của một chương trình brainfuck thành kiểu dữ liệu này. Vấn đề nảy sinh khi cố gắng phân tích cú pháp dấu ngoặc vuông một cách chính xác, bởi vì có một số nút thắt buộc phải làm như vậy để kết quả vòng lặp Instruction cuối cùng bên trong vòng lặp liên kết đến vòng lặp Control một lần nữa.

Thông tin sơ bộ hơn một chút. Xem this version on the github repo để biết tất cả chi tiết.

type TapeM = StateT Tape IO 
type TapeP = Program TapeM 
type TapeC = Cont TapeP 

branch :: Monad m => m Bool -> Program m -> Program m -> Program m 
branch cond trueBranch falseBranch = 
    Control ((\b -> if b then trueBranch else falseBranch) `liftM` cond) 

loopControl :: TapeP -> TapeP -> TapeP 
loopControl = branch (not <$> is0) 

Đây là những gì tôi đã cố gắng:

toProgram :: String -> TapeP 
toProgram = (`runCont` id) . toProgramStep 

liftI :: TapeM() -> String -> TapeC TapeP 
liftI i cs = Instruction i <$> toProgramStep cs 

toProgramStep :: String -> TapeC TapeP 
toProgramStep ('>':cs) = liftI right cs 
-- similarly for other instructions 
toProgramStep ('[':cs) = push (toProgramStep cs) 
toProgramStep (']':cs) = pop (toProgramStep cs) 

push :: TapeC TapeP -> TapeC TapeP 
push mcontinue = do 
    continue <- mcontinue 
    cont (\breakMake -> loopControl continue (breakMake continue)) 

pop :: TapeC TapeP -> TapeC TapeP 
pop mbreak = do 
    break <- mbreak 
    cont (\continueMake -> loopControl (continueMake break) break) 

tôi figured tôi bằng cách nào đó có thể sử dụng continuations để truyền đạt thông tin từ các trường hợp '[' đến ']' trường hợp và ngược lại, nhưng tôi không có một công ty đủ nắm bắt của Cont để thực sự làm bất cứ điều gì ngoài việc lắp ráp dự đoán hoang dã của một cái gì đó trông giống như nó có thể làm việc, như đã thấy ở trên với push và pop. Điều này biên dịch và chạy, nhưng kết quả là rác.

Có thể sử dụng Cont để thắt nút thích hợp cho tình huống này không? Nếu không, thì tôi nên sử dụng kỹ thuật nào để triển khai toProgram?

---

Lưu ý 1: Trước đây tôi đã gặp phải lỗi logic tinh tế: loopControl = branch is0 bị Bools đảo ngược.

Lưu ý 2: Tôi đã quản lý sử dụng MonadFix (theo đề xuất của jberryman) với State để đưa ra giải pháp (xem the current state of the github repository). Tôi vẫn muốn biết làm thế nào điều này có thể được thực hiện với Cont thay thế.

Lưu ý 3: Người cố vấn Racketeer của tôi đặt a similar Racket program cùng nhau cho tôi (xem tất cả các sửa đổi). Kỹ thuật ống/đường ống của anh ta có thể được dịch sang Haskell bằng cách sử dụng Cont không?

---

tl; dr tôi quản lý để thực hiện điều này bằng MonadFix, và người khác quản lý để làm điều đó bằng combinators tiếp tục vợt của. Tôi khá chắc chắn điều này có thể được thực hiện với Cont trong Haskell. Bạn có thể chỉ cho tôi làm thế nào?

Answer 1

Tiền đạo đi du lịch nhà nước với một đơn nguyên tiếp tục trông như thế này:

Cont (fw -> r) a 

Sau đó, các loại của các đối số để cont là

(a -> fw -> r) -> fw -> r 

Vì vậy, bạn có được một fw thông qua trong quá khứ mà bạn phải chuyển sang tiếp tục.

bang

ngược đi du lịch trông như thế này:

Cont (bw, r) a 

Sau đó, các loại của các đối số để cont là

(a -> (bw, r)) -> (bw, r) 

Tức là bạn nhận được một bw từ việc tiếp tục mà bạn phải chuyển sang quá khứ.

Đây có thể được kết hợp thành một sự tiếp nối đơn nguyên:

Cont (fw -> (bw, r)) a 

Có một bắt khi áp dụng này để phân tích cú pháp của bạn, bởi vì toProgramStep xây dựng chương trình theo hướng ngược lại, vì vậy danh sách các ']' điểm là trạng thái chuyển tiếp và danh sách các điểm '[' là trạng thái lạc hậu. Ngoài ra, tôi đã lười biếng và bỏ qua phần Có thể, sẽ bắt gặp các lỗi khớp mẫu trong openBrace và closeBrace.

type ParseState = Cont ([TapeP] -> ([TapeP], TapeP)) 

toProgram :: String -> TapeP 
toProgram = snd . ($ []) . (`runCont` (\a _ -> ([], a))) . toProgramStep 


openBrace :: ParseState TapeP -> ParseState TapeP 
openBrace mcontinue = do 
    continue <- mcontinue 
    cont $ \k (break:bs) -> let (cs, r) = k (loopControl continue break) bs in (continue:cs, r) 

closeBrace :: ParseState TapeP -> ParseState TapeP 
closeBrace mbreak = do 
    break <- mbreak 
    cont $ \k bs -> let (continue:cs, r) = k (loopControl continue break) (break:bs) in (cs, r) 

Answer 2

Rất lười biếng với câu trả lời này vì tôi không thoải mái với Cont, nhưng có lẽ là MonadFix có lẽ những gì bạn đang tìm kiếm? State là một ví dụ, mặc dù không Cont, và nó cho phép bạn làm những điều mà hình như (sử dụng "recursive do" notation):

{-# LANGUAGE DoReC#-} 
parseInst str = do 
    rec ctl <- parseInstructionsLinkingTo ctl str 

Đây là giải pháp tôi đã phát hiện ra cho thư viện các diễn viên của tôi: chúng tôi muốn có một hoạt động spawn trả về giá trị sinh ra hộp thư của diễn viên, nhưng sau đó làm cách nào để chúng tôi có thể khởi chạy diễn viên liên lạc lẫn nhau? Hoặc một diễn viên có quyền truy cập vào hộp thư của riêng mình?

Với MonadFix dụ phù hợp chúng ta có thể làm:

fork3 = do 
    rec mb1 <- spawn $ actorSpamming mb2 mb3 
     mb2 <- spawn $ actorSpamming mb1 mb2 
     mb3 <- spawn $ actorSpamming mb2 mb3 
    send "go" mb1 

Hope ở trên cung cấp cho bạn những ý tưởng.