Là một biến thể Lisp đầy đủ kiểu tĩnh có thể?

Question

Biến thể Lisp đầy đủ kiểu tĩnh có thể thực hiện được không? Liệu nó thậm chí có ý nghĩa cho một cái gì đó như thế này để tồn tại? Tôi tin rằng một trong những đức tính của ngôn ngữ Lisp là sự đơn giản của định nghĩa của nó. Kiểu gõ tĩnh có làm thỏa hiệp nguyên tắc cốt lõi này không?

Answer 1

Câu trả lời của tôi, không có mức độ tin cậy cao là có thể là. Ví dụ, nếu bạn nhìn vào một ngôn ngữ như SML và so sánh nó với Lisp, thì lõi chức năng của mỗi ngôn ngữ gần giống nhau. Kết quả là, nó không có vẻ như bạn sẽ có nhiều rắc rối áp dụng một số loại gõ tĩnh để cốt lõi của Lisp (ứng dụng chức năng và các giá trị nguyên thủy).

Câu hỏi của bạn có nghĩa là đầy đủ mặc dù và nơi tôi thấy một số sự cố sắp tới là phương pháp mã hóa dưới dạng dữ liệu. Các loại tồn tại ở mức trừu tượng hơn các biểu thức. Lisp không có sự phân biệt này - mọi thứ đều có cấu trúc "phẳng". Nếu chúng ta xem xét một số biểu thức E: T (trong đó T là một số biểu diễn của loại của nó), và sau đó chúng ta xem xét biểu thức này như là đồng bằng ol 'dữ liệu, sau đó chính xác là loại T ở đây? Vâng, đó là một loại! Loại là loại đơn đặt hàng cao hơn, vì vậy, hãy tiếp tục và nói điều gì đó về điều đó trong mã của chúng tôi:

E : T :: K 

Bạn có thể thấy tôi sẽ làm gì với điều này. Tôi chắc chắn bằng cách tách ra các loại thông tin từ mã nó sẽ có thể tránh loại này tự tham khảo của các loại, tuy nhiên điều đó sẽ làm cho các loại không phải là rất "lisp" trong hương vị của họ. Có lẽ có nhiều cách xung quanh điều này, mặc dù nó không rõ ràng với tôi mà sẽ là tốt nhất.

EDIT: Ồ, do đó, với một chút googling, tôi tìm thấy Qi, mà dường như rất giống với Lisp ngoại trừ việc nó được gõ tĩnh. Có lẽ đó là một nơi tốt để bắt đầu để xem nơi họ thực hiện thay đổi để có được gõ tĩnh trong đó.

Answer 2

Có, rất có thể, mặc dù hệ thống kiểu kiểu HM tiêu chuẩn thường là lựa chọn sai cho mã Lisp/Scheme thành ngữ nhất. Xem Typed Racket cho một ngôn ngữ gần đây là một "Full Lisp" (giống như Scheme, thực sự) với kiểu gõ tĩnh.

Answer 3

Dylan: http://visualization.dylan-user.org/diploma.pdf

Answer 4

Nếu tất cả các bạn muốn là một ngôn ngữ tĩnh đánh máy mà trông giống như Lisp, bạn có thể làm điều đó khá dễ dàng, bằng cách định nghĩa một cây cú pháp trừu tượng đại diện cho ngôn ngữ của bạn và sau đó lập bản đồ AST đó để Biểu thức S. Tuy nhiên, tôi không nghĩ tôi sẽ gọi kết quả là Lisp.

Nếu bạn muốn một cái gì đó thực sự có đặc điểm Lisp-y bên cạnh cú pháp, có thể thực hiện điều này bằng ngôn ngữ được nhập tĩnh. Tuy nhiên, có rất nhiều đặc điểm đối với Lisp rất khó để có được nhiều kiểu gõ tĩnh hữu ích. Để minh họa, chúng ta hãy xem cấu trúc danh sách, được gọi là cons, tạo thành khối xây dựng chính của Lisp.

Gọi danh sách khuyết điểm, mặc dù (1 2 3) trông giống như một, là một chút nhầm lẫn. Ví dụ, nó không phải là ở tất cả so sánh với một danh sách gõ tĩnh, như C++ 's std::list hoặc danh sách của Haskell. Đó là các danh sách liên kết một chiều, trong đó tất cả các ô cùng loại. Lisp vui vẻ cho phép (1 "abc" #\d 'foo). Ngoài ra, ngay cả khi bạn mở rộng danh sách được nhập tĩnh của mình để bao gồm danh sách danh sách, loại đối tượng này yêu cầu rằng mỗi phần tử của danh sách là danh sách phụ. Làm thế nào bạn sẽ đại diện cho ((1 2) 3 4) trong đó?

Lisp conses tạo thành một cây nhị phân, có lá (nguyên tử) và nhánh cây (conses). Hơn nữa, những chiếc lá của một cây như vậy có thể chứa bất kỳ loại Lisp nguyên tử (không đối lập) nào cả! Sự linh hoạt của cấu trúc này là những gì làm cho Lisp rất tốt trong việc xử lý tính toán biểu tượng, AST, và chuyển đổi mã Lisp chính nó!

Vậy làm cách nào để bạn mô hình cấu trúc như vậy bằng ngôn ngữ được nhập tĩnh? Hãy thử nó trong Haskell, trong đó có một hệ thống loại tĩnh cực kỳ mạnh mẽ và chính xác:

type Symbol = String 
data Atom = ASymbol Symbol | AInt Int | AString String | Nil 
data Cons = CCons Cons Cons 
      | CAtom Atom 

Vấn đề đầu tiên của bạn sẽ là phạm vi của loại Atom. Rõ ràng, chúng tôi đã không chọn một loại Atom đủ linh hoạt để trang trải tất cả các loại đối tượng mà chúng tôi muốn treo xung quanh trong các vật phẩm. Thay vì cố gắng mở rộng cấu trúc dữ liệu Atom như được liệt kê ở trên (bạn có thể thấy rõ ràng là giòn), giả sử chúng ta có một loại lớp ma thuật Atomic phân biệt tất cả các kiểu mà chúng ta muốn tạo ra nguyên tử. Sau đó, chúng ta có thể thử:

class Atomic a where ????? 
data Atomic a => Cons a = CCons Cons Cons 
          | CAtom a 

Nhưng điều này sẽ không làm việc vì nó đòi hỏi tất cả các nguyên tử trong cây là của cùng loại. Chúng tôi muốn chúng có thể khác với lá. Một cách tiếp cận tốt hơn yêu cầu sử dụng quantifiers hiện sinh Haskell của:

class Atomic a where ????? 
data Cons = CCons Cons Cons 
      | forall a. Atomic a => CAtom a 

Nhưng bây giờ bạn đến mấu chốt của vấn đề này. Bạn có thể làm gì với các nguyên tử trong loại cấu trúc này? Họ có chung cấu trúc nào có thể được mô hình hóa với Atomic a? Mức độ an toàn loại nào bạn được đảm bảo với loại như vậy? Lưu ý rằng chúng ta chưa thêm bất kỳ hàm nào vào lớp kiểu của chúng ta, và có một lý do chính đáng: các nguyên tử chia sẻ không có gì chung trong Lisp. Siêu mẫu của họ trong Lisp đơn giản được gọi là t (tức là trên cùng).

Để sử dụng chúng, bạn phải đưa ra các cơ chế để động coerce giá trị của nguyên tử vào thứ bạn thực sự có thể sử dụng. Và tại thời điểm đó, về cơ bản bạn đã triển khai thực hiện một hệ thống phụ được nhập động theo ngôn ngữ được đánh máy tĩnh của bạn! (Người ta không thể giúp đỡ, nhưng lưu ý một hệ quả có thể Greenspun's Tenth Rule of Programming.)

Lưu ý rằng Haskell cung cấp hỗ trợ cho chỉ như một dynamic subsystem với một loại Obj, sử dụng kết hợp với một loại Dynamic và Typeable class để thay thế lớp Atomic của chúng tôi, cho phép các giá trị tùy ý được lưu trữ với các loại của chúng, và sự ép buộc rõ ràng trở lại từ các kiểu đó. Đó là loại hệ thống bạn cần sử dụng để làm việc với các cấu trúc khuyết điểm của Lisp trong toàn bộ tính toàn bộ của chúng.

Những gì bạn cũng có thể làm là đi theo cách khác và nhúng một hệ thống con được nhập tĩnh trong một ngôn ngữ được nhập động cơ bản. Điều này cho phép bạn lợi ích của việc kiểm tra kiểu tĩnh đối với các phần của chương trình có thể tận dụng các yêu cầu loại nghiêm ngặt hơn. Điều này dường như là cách tiếp cận được thực hiện trong hình thức hạn chế của CMUCL là precise type checking, chẳng hạn.

Cuối cùng, có khả năng có hai hệ thống phụ riêng biệt, được nhập động và tĩnh, sử dụng lập trình kiểu hợp đồng để giúp điều hướng quá trình chuyển đổi giữa hai. Bằng cách đó, ngôn ngữ có thể chứa các tập quán của Lisp, nơi kiểm tra kiểu tĩnh sẽ có nhiều cản trở hơn là sự trợ giúp, cũng như việc sử dụng kiểm tra kiểu tĩnh sẽ thuận lợi. Đây là cách tiếp cận được thực hiện bởi Typed Racket, như bạn sẽ thấy từ các nhận xét theo sau.