Tại sao các kiểu dữ liệu ML/Haskell hữu ích để xác định "ngôn ngữ" như biểu thức số học?

Question

Đây là một câu hỏi mềm về các hệ thống kiểu tĩnh trong các ngôn ngữ chức năng như ngôn ngữ của họ ML. Tôi hiểu tại sao bạn cần các kiểu dữ liệu để mô tả các cấu trúc dữ liệu như danh sách và cây nhưng định nghĩa "các biểu thức" giống như các mệnh đề logic trong các kiểu dữ liệu dường như mang lại một số tiện lợi và không cần thiết. Ví dụ:

datatype arithmetic_exp = Constant of int 
         | Neg of arithmetic_exp 
         | Add of (arithmetic_exp * arithmetic_exp) 
         | Mult of (arithmetic_exp * arithmetic_exp) 

xác định tập hợp các giá trị, bạn có thể viết hàm eval. Bạn cũng có thể xác định 4 chức năng: const: int -> int, neg: int -> int, add: int * int -> int và mult: int * int -> int và sau đó biểu thức sắp xếp add (mult (const 3, neg 2), neg 4) sẽ cho bạn điều tương tự mà không mất bất kỳ sự bảo mật tĩnh nào. Biến chứng duy nhất là bạn phải làm bốn việc thay vì hai. Trong khi học SML và Haskell tôi đã cố gắng suy nghĩ về những tính năng nào cung cấp cho bạn một cái gì đó cần thiết và đó chỉ là một sự tiện lợi, vì vậy đây là lý do tại sao tôi hỏi. Tôi đoán điều này sẽ quan trọng nếu bạn muốn tách riêng quá trình đánh giá một giá trị từ chính giá trị đó nhưng tôi không chắc nó sẽ hữu ích ở đâu.

Cảm ơn rất nhiều.

Answer 1

Có tính nhị nguyên giữa mã hóa ban đầu/thứ tự đầu tiên/kiểu mã dữ liệu (còn gọi là nhúng sâu) và mã hóa dựa trên/cuối cùng/thứ tự cao hơn (hay còn gọi là nhúng nông). Bạn thực sự có thể thường sử dụng một typeclass của combinators thay vì một datatype (và chuyển đổi qua lại giữa hai).

Đây là một mô-đun hiển thị hai phương pháp:

{-# LANGUAGE GADTs, Rank2Types #-} 

module Expr where 

data Expr where 
    Val :: Int -> Expr 
    Add :: Expr -> Expr -> Expr 

class Expr' a where 
    val :: Int -> a 
    add :: a -> a -> a 

Bạn có thể thấy rằng hai định nghĩa một cách kỳ quái trông tương tự. Expr' a về cơ bản mô tả một đại số trên Expr có nghĩa là bạn có thể nhận được a trong số Expr nếu bạn có số Expr' a. Tương tự như vậy, bởi vì bạn có thể viết một ví dụ Expr' Expr, bạn có thể cụ thể hóa nhiệm kỳ loại forall a. Expr' a => a thành một giá trị cú pháp của kiểu Expr:

expr :: Expr' a => Expr -> a 
expr e = case e of 
    Val n -> val n 
    Add p q -> add (expr p) (expr q) 

instance Expr' Expr where 
    val = Val 
    add = Add 

expr' :: (forall a. Expr' a => a) -> Expr 
expr' e = e 

Cuối cùng, chọn một đại diện khác hơn thực sự phụ thuộc vào những gì bạn Trọng tâm chính là: nếu bạn muốn kiểm tra cấu trúc của biểu thức (ví dụ: nếu bạn muốn tối ưu hóa/biên dịch nó), sẽ dễ dàng hơn nếu bạn có quyền truy cập vào một AST. Mặt khác, nếu bạn chỉ quan tâm đến việc tính toán một biến thể bằng cách sử dụng nếp gấp (ví dụ: chiều sâu của biểu thức hoặc đánh giá của nó), mã hóa đơn đặt hàng cao hơn sẽ thực hiện.

Answer 2

ADT ở dạng bạn có thể kiểm tra và thao tác theo những cách khác ngoài việc đơn giản là đánh giá nó. Một khi bạn ẩn tất cả các dữ liệu thú vị trong một cuộc gọi chức năng, không còn bất cứ điều gì bạn có thể làm với nó nhưng đánh giá nó. Hãy xem xét định nghĩa này, tương tự như định nghĩa trong câu hỏi của bạn, nhưng với một thuật ngữ Var để biểu diễn các biến và với các thuật ngữ Mul và Neg được loại bỏ để tập trung vào việc bổ sung.

data Expr a = Constant a 
      | Add (Expr a) (Expr a) 
      | Var String 
      deriving Show 

Chức năng rõ ràng để viết là eval, tất nhiên. Nó đòi hỏi một cách để tìm kiếm giá trị của biến và đơn giản:

-- cheating a little bit by assuming all Vars are defined 
eval :: Num a => Expr a -> (String -> a) -> a 
eval (Constant x) _env = x 
eval (Add x y) env = eval x env + eval y env 
eval (Var x) env = env x 

Nhưng giả sử bạn chưa có ánh xạ biến. Bạn có một biểu thức lớn mà bạn sẽ đánh giá nhiều lần, cho các lựa chọn khác nhau của biến.Và một số chức năng đệ quy ngớ ngẩn xây dựng một biểu hiện như:

Add (Constant 1) 
    (Add (Constant 1) 
     (Add (Constant 1) 
       (Add (Constant 1) 
        (Add (Constant 1) 
         (Add (Constant 1) 
          (Var "x")))))) 

Nó sẽ là lãng phí để recompute 1+1+1+1+1+1 mỗi khi bạn đánh giá này: nó sẽ không được tốt đẹp nếu đánh giá của bạn có thể nhận ra rằng đây chỉ là một cách khác để viết Add (Constant 6) (Var "x")?

Vì vậy, bạn viết trình tối ưu hóa biểu thức, chạy trước bất kỳ biến nào khả dụng và cố gắng đơn giản hóa các biểu thức. Có nhiều quy tắc đơn giản hóa bạn có thể áp dụng, tất nhiên; dưới đây tôi đã thực hiện chỉ hai cái rất dễ để minh họa điểm.

simplify :: Num a => Expr a -> Expr a 
simplify (Add (Constant x) (Constant y)) = Constant $ x + y 
simplify (Add (Constant x) (Add (Constant y) z)) = simplify $ Add (Constant $ x + y) z 
simplify x = x 

Bây giờ biểu thức ngớ ngẩn của chúng ta trông như thế nào?

> simplify $ Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Var "x")))))) 
Add (Constant 6) (Var "x") 

Tất cả những thứ không cần thiết đã được loại bỏ, và bây giờ bạn có một biểu thức sạch đẹp để thử cho các giá trị khác nhau của x.

Bạn làm điều tương tự như thế nào với biểu diễn biểu thức này trong các hàm? Bạn không thể, bởi vì không có "biểu mẫu trung gian" giữa đặc tả ban đầu của biểu thức và đánh giá cuối cùng của nó: bạn chỉ có thể xem biểu thức dưới dạng một cuộc gọi hàm duy nhất, đục. Đánh giá nó ở một giá trị cụ thể của x nhất thiết phải đánh giá từng biểu thức con một lần nữa và không có cách nào để loại bỏ chúng.

Dưới đây là một phần mở rộng của các loại chức năng mà bạn đề xuất trong câu hỏi của bạn, một lần nữa được làm giàu với các biến:

type FExpr a = (String -> a) -> a 

lit :: a -> FExpr a 
lit x _env = x 

add :: Num a => FExpr a -> FExpr a -> FExpr a 
add x y env = x env + y env 

var :: String -> FExpr a 
var x env = env x 

với sự biểu hiện ngớ ngẩn tương tự để đánh giá nhiều lần:

sample :: Num a => FExpr a 
sample = add (lit 1) 
      (add (lit 1) 
        (add (lit 1) 
         (add (lit 1) 
          (add (lit 1) 
           (add (lit 1) 
             (var "x")))))) 

Nó hoạt động như mong đợi :

> sample $ \_var -> 5 
11 

Nhưng nó phải làm một loạt các bổ sung mỗi khi bạn cố gắng nó cho một khác nhau x, mặc dù việc bổ sung và biến là chủ yếu là không liên quan. Và không có cách nào bạn có thể đơn giản hóa cây biểu thức. Bạn không thể đơn giản hóa nó trong khi xác định nó: nghĩa là, bạn không thể làm cho add thông minh hơn, bởi vì nó không thể kiểm tra đối số của nó: các đối số của nó là các hàm, theo như add có liên quan, có thể làm bất cứ điều gì . Và bạn không thể đơn giản hóa nó sau khi xây dựng nó, hoặc: tại thời điểm đó bạn chỉ có một hàm mờ mất trong một hàm tra cứu biến và tạo ra một giá trị.

Bằng cách lập mô hình các phần quan trọng của sự cố của bạn dưới dạng các loại dữ liệu theo đúng nghĩa của chúng, bạn làm cho chúng trở thành giá trị mà chương trình của bạn có thể thao tác thông minh. Nếu bạn để chúng như các hàm, bạn sẽ có một chương trình ngắn hơn, ít mạnh hơn, bởi vì bạn khóa tất cả thông tin bên trong lambdas mà chỉ có GHC có thể thao tác.

Và một khi bạn đã viết nó bằng ADT, sẽ không khó để thu gọn đại diện đó trở lại đại diện dựa trên hàm ngắn hơn nếu bạn muốn. Tức là, có thể có một chức năng tốt là loại

convert :: Expr a -> FExpr a 

Nhưng trên thực tế, chúng tôi đã làm điều này! Đó chính là loại mà eval có. Bạn chỉ có thể không nhận thấy vì bí danh loại FExpr, không được sử dụng trong định nghĩa của eval.

Vì vậy, theo cách nào đó, biểu diễn ADT tổng quát hơn và mạnh mẽ hơn, hoạt động như một cái cây mà bạn có thể gấp lại theo nhiều cách khác nhau. Một trong những cách đó là đánh giá nó, theo cách chính xác của biểu diễn dựa trên hàm. Nhưng cũng có những người khác:

• Đơn giản hóa các biểu hiện trước khi đánh giá nó
• Sản xuất một danh sách tất cả các biến phải được xác định cho biểu thức này được hình thành cũng
• Đếm cách sâu sắc lồng phần sâu nhất của cây, để ước tính nhiều ngăn xếp khung làm thế nào một đánh giá có thể cần
• Chuyển đổi biểu thức vào một string xấp xỉ một biểu Haskell bạn có thể gõ để có được kết quả tương tự

Vì vậy, nếu có thể bạn muốn làm việc với ADT giàu thông tin miễn là bạn có thể, và sau đó cuối cùng gấp cây thành một hình thức nhỏ gọn hơn một khi bạn có một cái gì đó cụ thể để làm với nó.