Cách đúng để đánh máy trừu tượng trừu tượng lambda phụ thuộc bằng cách sử dụng 'ràng buộc' là gì?

Question

Tôi đang triển khai một ngôn ngữ đơn giản, được đánh máy, tương tự như một described by Lennart Augustsson, trong khi cũng sử dụng bound để quản lý các ràng buộc.

Khi typechecking một thuật ngữ lambda phụ thuộc, chẳng hạn như λt:* . λx:t . x, tôi cần phải:

1. "Enter" lambda chất kết dính bên ngoài, bởi instantiating t-một cái gì đó
2. Typecheck λx:t . x, năng suất ∀x:t . t
3. Pi-trừu tượng số t, có lãi ∀t:* . ∀x:t . t

Nếu lambda không phụ thuộc, tôi có thể lấy đi bằng cách instantiating t với loại ở bước 1, vì loại này là tất cả những gì tôi cần biết về biến trong khi gõ vào bước 2. Nhưng ở bước 3 tôi thiếu thông tin để quyết định biến nào sẽ trừu tượng hóa.

Tôi có thể giới thiệu nguồn cung cấp tên mới và tạo nhanh t với Bound.Name.Name chứa cả loại và tên duy nhất. Nhưng tôi nghĩ rằng với bound tôi không cần phải tạo tên mới.

Tôi có thiếu giải pháp thay thế không?

Answer 1

Chúng tôi cần một số loại ngữ cảnh để theo dõi các đối số lambda. Tuy nhiên, chúng tôi không nhất thiết cần phải khởi tạo chúng, vì bound cung cấp cho chúng tôi chỉ số de Bruijn và chúng tôi có thể sử dụng các chỉ mục đó để lập chỉ mục vào ngữ cảnh.

Thực tế việc sử dụng các chỉ mục có liên quan một chút, vì máy móc loại cấp phản ánh kích thước của phạm vi hiện tại (hoặc nói cách khác là chiều sâu hiện tại trong biểu thức) thông qua việc làm tổ của Var -s . Nó đòi hỏi việc sử dụng đệ quy đa hình hoặc GADT. Nó cũng ngăn cản chúng ta lưu trữ bối cảnh trong một đơn vị nhà nước (vì kích thước và do đó loại bối cảnh thay đổi khi chúng ta recurse). Tôi tự hỏi liệu chúng ta có thể sử dụng một đơn vị trạng thái được lập chỉ mục hay không; nó sẽ là một thử nghiệm thú vị. Nhưng tôi lạc đề.

Giải pháp đơn giản nhất là để đại diện cho bối cảnh là một hàm:

type TC a = Either String a -- our checker monad 
type Cxt a = a -> TC (Type a) -- the context 

Các đầu vào a về cơ bản là một chỉ số de Bruijn, và chúng ta nhìn lên một loại bằng cách áp dụng các chức năng để chỉ số. Chúng ta có thể xác định bối cảnh trống theo cách sau:

emptyCxt :: Cxt a 
emptyCxt = const $ Left "variable not in scope" 

Và chúng ta có thể mở rộng bối cảnh:

consCxt :: Type a -> Cxt a -> Cxt (Var() a) 
consCxt ty cxt (B()) = pure (F <$> ty) 
consCxt ty cxt (F a) = (F <$>) <$> cxt a 

Kích thước của bối cảnh được mã hóa trong Var làm tổ. Sự gia tăng kích thước là rõ ràng ở đây trong kiểu trả về.

Bây giờ chúng tôi có thể viết trình kiểm tra loại. Điểm chính ở đây là chúng tôi sử dụng fromScope và toScope để có được chất kết dính, và chúng tôi mang theo một cách thích hợp mở rộng Cxt (có loại dòng lên chỉ hoàn hảo).

data Term a 
    = Var a 
    | Star -- or alternatively, "Type", or "*" 
    | Lam (Type a) (Scope() Term a) 
    | Pi (Type a) (Scope() Term a) 
    | App (Type a) (Term a) 
    deriving (Show, Eq, Functor) 

-- boilerplate omitted (Monad, Applicative, Eq1, Show1 instances) 

-- reduce to normal form 
rnf :: Term a -> Term a 
rnf = ... 

-- Note: IIRC "Simply easy" and Augustsson's post reduces to whnf 
-- when type checking. I use here plain normal form, because it 
-- simplifies the presentation a bit and it also works fine. 

-- We rely on Bound's alpha equality here, and also on the fact 
-- that we keep types in normal form, so there's no need for 
-- additional reduction. 
check :: Eq a => Cxt a -> Type a -> Term a -> TC() 
check cxt want t = do 
    have <- infer cxt t 
    when (want /= have) $ Left "type mismatch" 

infer :: Eq a => Cxt a -> Term a -> TC (Type a) 
infer cxt = \case 
    Var a -> cxt a 
    Star -> pure Star -- "Type : Type" system for simplicity 
    Lam ty t -> do 
    check cxt Star ty 
    let ty' = rnf ty 
    Pi ty' . toScope <$> infer (consCxt ty' cxt) (fromScope t) 
    Pi ty t -> do 
    check cxt Star ty 
    check (consCxt (rnf ty) cxt) Star (fromScope t) 
    pure Star 
    App f x -> 
    infer cxt f >>= \case 
     Pi ty t -> do 
     check cxt ty x 
     pure $ rnf (instantiate1 x t) 
     _ -> Left "can't apply non-function" 

Đây là the working code containing các định nghĩa ở trên. Tôi hy vọng tôi không làm hỏng nó quá tệ.