2012-02-06 48 views
7

Hãy xem xét các chức năng SML sau:Chức năng nào áp dụng đối số của chính nó?

fn x => x x 

này tạo ra các lỗi sau (Standard ML New Jersey v110.72):

stdIn:1.9-1.12 Error: operator is not a function [circularity] 
    operator: 'Z 
    in expression: 
    x x 

tôi có thể sắp xếp xem tại sao điều này là không được phép - - đối với một, tôi không thực sự chắc chắn làm thế nào để viết ra loại của nó sẽ được - nhưng nó không hoàn toàn vô nghĩa; ví dụ, tôi có thể truyền chức năng nhận diện cho nó và lấy lại nó.

Có tên cho chức năng này không? (Có cách nào để diễn tả nó trong SML không?)

+0

Nếu có ai quan tâm, tôi thấy rằng điều này được gọi là [U Kết hợp (xem dưới cùng của trang)] (http://www.ucombinator.org/), nhưng không thể tìm thấy nhiều hơn về nó. –

+0

Tôi không biết nó được gọi là bộ kết hợp U, nhưng như trang đó nói, nó được sử dụng để xây dựng chương trình không kết thúc (rõ ràng là ngắn nhất) của phép tính lambda chưa được phân loại mà tôi đưa vào câu trả lời của tôi. –

Trả lời

7

Không có cách nào để diễn tả chức năng này bằng ngôn ngữ có hệ thống kiểu giống ML. Ngay cả với chức năng nhận dạng nó sẽ không hoạt động, bởi vì x đầu tiên và thứ hai trong x x sẽ phải là trường hợp khác nhau của chức năng đó, loại (_a -> _a) -> (_a -> _a)_a -> _a, tương ứng, đối với một số loại _a.

Trong thực tế, hệ thống loại được thiết kế để ngăn cấm các cấu trúc như

(λx . x x) (λx . x x) 

trong giải tích lambda untyped. Trong Đề án ngôn ngữ kiểu động, bạn có thể viết hàm này:

(define (apply-to-self x) (x x)) 

và nhận được kết quả mong đợi

> (define (id x) x) 
> (eq? (apply-to-self id) id) 
#t 
+0

"bởi vì x đầu tiên và thứ hai trong x x sẽ phải là ** trường hợp khác nhau ** của chức năng đó": ra khỏi tò mò, những gì về ngôn ngữ với đánh giá lười biếng? Bên cạnh đó, tôi không chắc chắn có bất cứ điều gì giống như "dụ" trong SML (trừ khi có những tác dụng phụ). Vấn đề chỉ là một vấn đề đánh máy (không có loại, thường không có ý nghĩa, trong khi không phải luôn luôn). – Hibou57

+1

@ Hibou57 Ví dụ, tôi có nghĩa là một instantiation cụ thể-typed của một chức năng chung chung. –

4

Chức năng như thế này thường gặp phải trong combinators điểm cố định. ví dụ. một hình thức của Y combinator được viết λf.(λx.f (x x)) (λx.f (x x)). Các bộ phối hợp điểm cố định được sử dụng để thực hiện phép đệ quy chung trong phép tính lambda không định dạng mà không có bất kỳ cấu trúc đệ quy bổ sung nào, và đây là một phần của những gì làm cho phép tính lambda chưa hoàn thành Turing-complete.

Khi mọi người phát triển simply-typed lambda calculus, đó là một hệ thống kiểu tĩnh ngây thơ trên đỉnh phép tính lambda, họ phát hiện ra rằng không còn khả năng viết các hàm như vậy nữa. Trong thực tế, không thể thực hiện đệ quy chung trong phép tính lambda được đánh máy đơn giản; và do đó, tính toán lambda đơn giản, không còn là Turing-complete. (Một hiệu ứng phụ thú vị là các chương trình trong tính toán lambda đơn giản đã gõ luôn luôn là chấm dứt.)

Các ngôn ngữ lập trình tĩnh được tạo sẵn để khắc phục vấn đề, chẳng hạn như các hàm đệ quy được đặt tên (được xác định với val rec hoặc fun) và được đặt tên theo kiểu dữ liệu đệ quy.

Vẫn có thể sử dụng kiểu dữ liệu đệ quy để mô phỏng thứ gì đó giống như những gì bạn muốn, nhưng nó không đẹp.

Về cơ bản, bạn muốn xác định loại như 'a foo = 'a foo -> 'a; tuy nhiên, điều này là không được phép. Bạn thay vì bọc nó trong một datatype: datatype 'a foo = Wrap of ('a foo -> 'a);

datatype 'a foo = Wrap of ('a foo -> 'a); 
fun unwrap (Wrap x) = x; 

Về cơ bản, Wrapunwrap được sử dụng để chuyển đổi giữa 'a foo'a foo -> 'a, và ngược lại.

Bất cứ khi nào bạn cần tự gọi một hàm, thay vì x x, bạn phải viết rõ ràng (unwrap x) x (hoặc unwrap x x); tức là unwrap biến nó thành một hàm mà sau đó bạn có thể áp dụng cho giá trị ban đầu.

P.S. Một ngôn ngữ ML khác, OCaml, có một tùy chọn để kích hoạt các kiểu đệ quy (thường bị vô hiệu hóa); nếu bạn chạy trình thông dịch hoặc trình biên dịch với cờ -rectypes, thì có thể viết những thứ như fun x -> x x. Về cơ bản, đằng sau hậu trường, trình kiểm tra kiểu sẽ tìm ra những nơi bạn cần "quấn" và "unwrap" loại đệ quy, sau đó chèn chúng cho bạn. Tôi không biết bất kỳ việc triển khai ML tiêu chuẩn nào có chức năng đệ quy kiểu tương tự.

+0

“Tôi không biết bất kỳ việc triển khai ML tiêu chuẩn nào có chức năng kiểu đệ quy tương tự”: định nghĩa của SML không cho phép nó, vì vậy sẽ không có triển khai nào thực hiện điều này. Sự cần thiết phải bọc nó trong một kiểu dữ liệu có thể có ý nghĩa. Nhìn vào một định nghĩa kiểu như ''a f =' a f -> 'a' làm cho tôi nghĩ rằng đó là một quy tắc viết lại hoặc đánh giá nhiều hơn một loại. Nhưng có thể tôi là thiên vị về điều này. – Hibou57

Các vấn đề liên quan