Sử dụng trạng thái Haskell monad một mã có mùi không?

Question

Chúa tôi ghét thuật ngữ "mã ngửi", nhưng tôi không thể nghĩ ra bất cứ điều gì chính xác hơn.

Tôi đang thiết kế một ngôn ngữ cấp cao & trình biên dịch sang Whitespace trong thời gian rảnh rỗi để tìm hiểu về xây dựng trình biên dịch, thiết kế ngôn ngữ và lập trình hàm (trình biên dịch được viết bằng Haskell).

Trong giai đoạn tạo mã của trình biên dịch, tôi phải duy trì dữ liệu "trạng thái" khi tôi duyệt qua cây cú pháp. Ví dụ, khi biên dịch các câu lệnh kiểm soát dòng chảy, tôi cần phải tạo các tên duy nhất cho các nhãn để nhảy tới (các nhãn được tạo ra từ một bộ đếm được cập nhật, cập nhật, & trả về và giá trị cũ của bộ đếm không bao giờ được sử dụng lại). Một ví dụ khác là khi tôi bắt gặp các chuỗi ký tự trong dòng trong cây cú pháp, chúng cần được chuyển đổi vĩnh viễn thành các biến heap (trong khoảng trắng, các chuỗi được lưu trữ tốt nhất trên vùng heap). Tôi hiện đang gói toàn bộ mô-đun tạo mã trong trình đơn trạng thái để xử lý việc này.

Tôi đã nói rằng việc viết trình biên dịch là một vấn đề rất phù hợp với mô hình chức năng, nhưng tôi thấy rằng tôi đang thiết kế nó theo cùng cách tôi sẽ thiết kế nó trong C (bạn thực sự có thể viết C trong bất kỳ ngôn ngữ nào - ngay cả Haskell w/tiểu bang monads).

Tôi muốn tìm hiểu cách suy nghĩ trong Haskell (đúng hơn, trong mô hình chức năng) - không phải trong C với cú pháp Haskell. Tôi có nên thực sự cố gắng để loại bỏ/giảm thiểu việc sử dụng các đơn nguyên trạng thái, hoặc nó là một chức năng hợp pháp "mẫu thiết kế"?

Answer 1

Tôi muốn nói rằng trạng thái nói chung không phải là mùi mã, miễn là nó được giữ nhỏ và được kiểm soát tốt. Điều này có nghĩa là sử dụng các đơn vị như State, ST hoặc custom-built, hoặc chỉ có một cấu trúc dữ liệu chứa dữ liệu trạng thái mà bạn chuyển đến một vài nơi, không phải là một điều xấu.(Trên thực tế, monads chỉ là hỗ trợ trong việc làm chính xác điều này!) Tuy nhiên, có nhà nước mà đi khắp nơi (có, điều này có nghĩa là bạn, IO monad!) Là một mùi hôi.

Một ví dụ khá rõ ràng về điều này là khi nhóm của tôi đang làm việc trên mục nhập của chúng tôi cho ICFP Programming Contest 2009 (mã có sẵn tại git: //git.cynic.net/haskell/icfp-contest-2009). Chúng tôi đã kết thúc với một số bộ phận mô-đun khác nhau như sau:

• VM: máy ảo chạy chương trình mô phỏng
• Bộ xử lý: bộ khác nhau của thói quen mà đọc đầu ra của mô phỏng và tạo ra đầu vào điều khiển mới
• Giải pháp: tạo tệp giải pháp dựa trên đầu ra của các bộ điều khiển
• Trình hiển thị: một số bộ định tuyến khác nhau đọc cả cổng đầu vào và đầu ra và tạo ra một số loại trực quan hoặc nhật ký về những gì đang diễn ra đã tiến hành

Mỗi có nhà nước riêng của mình, và tất cả đều tương tác theo những cách khác nhau thông qua các giá trị đầu vào và đầu ra của VM. Chúng tôi có nhiều bộ điều khiển và bộ hiển thị khác nhau, mỗi bộ điều khiển có một loại trạng thái khác nhau.

Điểm mấu chốt ở đây là những người bên trong của bất kỳ trạng thái đặc biệt được giới hạn trong các module đặc biệt của riêng mình, và mỗi mô-đun không biết gì về thậm chí sự tồn tại của nhà nước đối với các module khác. Bất kỳ tập hợp mã và dữ liệu trạng thái cụ thể nào nói chung chỉ dài vài chục dòng, với một số mục dữ liệu trong tiểu bang.

Tất cả điều này được dán lại với nhau trong một chức năng nhỏ của khoảng một chục dòng mà không có quyền truy cập vào nội bộ của bất kỳ tiểu bang nào, và chỉ được gọi đúng thứ tự theo thứ tự thích hợp. thông qua một số lượng rất hạn chế thông tin bên ngoài cho mỗi mô-đun (cùng với trạng thái trước đó của mô-đun, tất nhiên).

Khi nhà nước được sử dụng một cách hạn chế như vậy, và các hệ thống kiểu đang ngăn cản bạn vô tình sửa đổi nó, nó khá dễ dàng để xử lý. Đó là một trong những nét đẹp của Haskell mà nó cho phép bạn làm điều này.

Một câu trả lời cho biết, "Không sử dụng đơn thuần". Theo quan điểm của tôi, đây chính xác là ngược lại. Monads là một cấu trúc điều khiển, trong số những thứ khác, có thể giúp bạn giảm thiểu số lượng mã chạm vào trạng thái. Nếu bạn xem xét các trình phân tích cú pháp đơn thuần như một ví dụ, trạng thái của phân tích cú pháp (ví dụ, văn bản được phân tích cú pháp, bao nhiêu người đã nhận được nó, bất kỳ cảnh báo nào đã tích lũy, vv) phải chạy qua mọi bộ kết hợp được sử dụng trong trình phân tích cú pháp . Tuy nhiên, sẽ chỉ có một vài combinators thực sự thao túng nhà nước một cách trực tiếp; bất cứ điều gì khác sử dụng một trong các chức năng này. Điều này cho phép bạn thấy rõ ràng và ở một nơi tất cả một số lượng nhỏ mã có thể thay đổi trạng thái và dễ dàng hơn lý do về cách mã có thể được thay đổi, một lần nữa giúp việc xử lý dễ dàng hơn.

Answer 2

Vâng, đừng sử dụng monads. Sức mạnh của lập trình chức năng là độ tinh khiết chức năng và tái sử dụng của chúng. Có bài báo này là một giáo sư của tôi đã từng viết và anh ấy là một trong những người đã giúp xây dựng Haskell.

Giấy được gọi là "Why functional programming matters", tôi khuyên bạn nên đọc qua nó. Đó là một đọc tốt.

Answer 3

hãy cẩn thận về thuật ngữ tại đây. Nhà nước không phải là mỗi se xấu; ngôn ngữ chức năng có trạng thái. "Mùi mã" là gì khi bạn thấy mình muốn gán các giá trị biến và thay đổi chúng.

Tất nhiên, đơn vị trạng thái Haskell chỉ có lý do đó - như với I/O, nó cho phép bạn làm những việc không an toàn và không chức năng trong bối cảnh hạn chế.

Vì vậy, có, nó có thể là một mùi mã.

Answer 4

Bạn đã xem Attribute grammars (AG) chưa? (Thông tin thêm về wikipedia và article trong Trình đọc Monad)?

Với AG, bạn có thể thêm thuộc tính vào cây cú pháp. Các thuộc tính này được tách riêng trong các thuộc tính được tổng hợp và được thừa kế.

thuộc tính tổng hợp những thứ bạn tạo ra (hoặc tổng hợp) từ cây cú pháp của bạn, đây có thể là mã được tạo, hoặc tất cả các ý kiến, hoặc bất cứ điều gì khác bạn quan tâm.

thuộc tính thừa kế là đầu vào cho cây cú pháp của bạn, đây có thể là môi trường hoặc danh sách các nhãn để sử dụng trong quá trình tạo mã.

Tại Đại học Utrecht, chúng tôi sử dụng Attribute Grammar System (UUAGC) để viết trình biên dịch.Đây là bộ xử lý trước tạo mã haskell (.hs tệp) từ các tệp .ag được cung cấp.

---

Mặc dù, nếu bạn vẫn đang học Haskell thì có lẽ đây không phải là lúc để bắt đầu học thêm một lớp trừu tượng nào khác.

Trong trường hợp đó, bạn có thể viết các loại mã mà các thuộc tính văn phạm tiếng tạo ra cho bạn, ví dụ:

data AbstractSyntax = Literal Int | Block AbstractSyntax 
        | Comment String AbstractSyntax 

compile :: AbstractSyntax -> [Label] -> (Code, Comments) 
compile (Literal x) _  = (generateCode x, []) 
compile (Block ast) (l:ls) = let (code', comments) = compile ast ls 
          in (labelCode l code', comments) 
compile (Comment s ast) ls = let (code, comments') = compile ast ls 
          in (code, s : comments') 

generateCode :: Int -> Code 
labelCode :: Label -> Code -> Code 

Answer 5

Tôi đã viết nhiều trình biên dịch trong Haskell, và một đơn nguyên nhà nước là một giải pháp hợp lý với nhiều vấn đề về trình biên dịch. Nhưng bạn muốn giữ cho nó trừu tượng --- không làm cho nó rõ ràng bạn đang sử dụng một đơn nguyên.

Đây là một ví dụ từ trình biên dịch Glasgow Haskell (mà tôi đã làm không viết; Tôi chỉ làm việc xung quanh một vài cạnh), nơi chúng tôi xây dựng biểu đồ dòng điều khiển. Dưới đây là những cách cơ bản để làm cho đồ thị:

empyGraph :: Graph 
mkLabel  :: Label -> Graph 
mkAssignment :: Assignment -> Graph -- modify a register or memory 
mkTransfer :: ControlTransfer -> Graph -- any control transfer 
(<*>)  :: Graph -> Graph -> Graph 

Nhưng khi bạn đã phát hiện ra, việc duy trì một nguồn cung cấp của nhãn duy nhất là tẻ nhạt lúc tốt nhất, vì vậy chúng tôi cung cấp các chức năng này cũng như:

withFreshLabel :: (Label -> Graph) -> Graph 
mkIfThenElse :: (Label -> Label -> Graph) -- branch condition 
      -> Graph -- code in the 'then' branch 
      -> Graph -- code in the 'else' branch 
      -> Graph -- resulting if-then-else construct 

Các toàn bộ điều Graph là một loại trừu tượng, và người dịch chỉ vui vẻ xây dựng các đồ thị theo kiểu thời trang hoàn toàn chức năng, mà không nhận thức được rằng bất cứ điều gì monadic đang diễn ra. Sau đó, khi đồ thị được xây dựng cuối cùng, để biến nó thành một kiểu dữ liệu đại số, chúng ta có thể tạo mã từ, chúng ta cung cấp cho nó một nhãn duy nhất, chạy đơn nguyên trạng thái và kéo ra cấu trúc dữ liệu.

Đơn vị trạng thái bị ẩn bên dưới; mặc dù nó không được tiếp xúc với khách hàng, định nghĩa về Graph là một cái gì đó như thế này:

type Graph = RealGraph -> [Label] -> (RealGraph, [Label]) 

hoặc một chút chính xác hơn

type Graph = RealGraph -> State [Label] RealGraph 
    -- a Graph is a monadic function from a successor RealGraph to a new RealGraph 

Với đơn nguyên trạng thái ẩn đằng sau một lớp trừu tượng, nó không có mùi ở tất cả!

Answer 6

Có thể là bạn có thể muốn một functor applicative thay vì một đơn nguyên :

http://www.haskell.org/haskellwiki/Applicative_functor

Tôi nghĩ rằng giấy ban đầu giải thích nó tốt hơn so với wiki, tuy nhiên:

http://www.soi.city.ac.uk/~ross/papers/Applicative.html

Answer 7

Nói chung, bạn nên cố gắng tránh trạng thái bất cứ khi nào có thể, nhưng điều đó không phải lúc nào cũng thực tế. Applicative làm cho mã hiệu quả đẹp hơn và chức năng hơn, đặc biệt là mã cây traversal có thể hưởng lợi từ kiểu này. Đối với vấn đề tạo tên, bây giờ có một gói khá tốt đẹp: value-supply.

Answer 8

Tôi không nghĩ rằng việc sử dụng Monad trạng thái là một mã nguồn khi nó được sử dụng để mô hình nhà nước.

Nếu bạn cần trạng thái chuỗi thông qua các hàm của mình, bạn có thể làm điều này một cách rõ ràng, lấy trạng thái làm đối số và trả về trong mỗi hàm. State Monad cung cấp một trừu tượng tốt: nó vượt qua trạng thái dọc theo cho bạn và cung cấp rất nhiều chức năng hữu ích để kết hợp các chức năng yêu cầu nhà nước. Trong trường hợp này, việc sử dụng Monad của Nhà nước (hoặc Đơn đăng ký) không phải là một mùi mã.

Tuy nhiên, nếu bạn sử dụng Trạng thái đơn vị để mô phỏng kiểu lập trình bắt buộc trong khi giải pháp chức năng đủ, bạn chỉ đang làm mọi thứ phức tạp.