Mọi ngôn ngữ chức năng có thể lười biếng không?

Question

Trong một ngôn ngữ chức năng, chức năng là công dân hạng nhất và do đó gọi chúng không phải là điều duy nhất tôi có thể làm. Tôi cũng có thể cất giữ chúng.

Bây giờ khi tôi có một ngôn ngữ, theo mặc định, theo mặc định, tôi vẫn không bị buộc phải đánh giá một cuộc gọi hàm. Tôi có tùy chọn để lưu trữ hàm và thông số của hàm, ví dụ: trong một tuple để đánh giá sau này.

Vì vậy, thay vì

x = f a b c 

tôi làm điều gì đó như

x = (f,a,b,c) 

Và sau đó, tôi có thể đánh giá điều này với một cái gì đó giống như

eval (f,a,b,c) = f a b c 

Vâng, có lẽ là nhiều hơn để nó, bởi vì tôi muốn đánh giá từng chức năng không được đánh giá chỉ một lần, nhưng có vẻ như với tôi, rằng điều này cũng có thể được giải quyết với cấu trúc dữ liệu vốn có chút huyền ảo hơn là một bộ dữ liệu.

Nghịch đảo cũng có vẻ như vậy, vì ví dụ: trong Haskell, mà là lười biếng được mặc định tôi có thể thực thi đánh giá với seq hoặc BangPatterns.

Vậy là nó đúng để nói, rằng tất cả các ngôn ngữ chức năng có tiềm năng của lười biếng, nhưng hầu hết trong số họ chỉ là không lười biếng theo mặc định và do đó cần thêm nỗ lực lập trình để gọi một chức năng một cách lười biếng, trong khi Haskell là lười biếng theo mặc định và yêu cầu nỗ lực lập trình bổ sung để gọi hàm theo cách nghiêm ngặt?

Nếu trường hợp đó xảy ra, điều gì sẽ khó khăn hơn cho người lập trình: viết lời gọi hàm lười trong ngôn ngữ khắt khe hoặc viết các cuộc gọi chức năng nghiêm ngặt bằng ngôn ngữ lười biếng?

Lưu ý: Simon P. Jone nghiêm túc khi nói: "phiên bản tiếp theo của haskell sẽ nghiêm ngặt". Lần đầu tiên tôi nghĩ rằng đây là một trò đùa. Nhưng bây giờ tôi nghĩ rằng nghiêm ngặt theo mặc định không phải là tất cả những gì xấu miễn là bạn có thể lười biếng nếu cần thiết.

Answer 1

Câu trả lời là có đủ điều kiện. Trực giác của bạn rằng sự lười biếng có thể được thực hiện bằng một ngôn ngữ nghiêm ngặt, nơi các hàm là các đối tượng hạng nhất là chính xác. Nhưng đi vào chi tiết cho thấy một số sự tinh tế. Hãy lấy một ngôn ngữ chức năng (theo đó tôi ngụ ý một ngôn ngữ nơi mà các hàm có thể được xây dựng và thao tác như các đối tượng hạng nhất, như trong phép tính lambda), nơi ứng dụng hàm là nghiêm ngặt (tức là hàm¹ và đối số của nó).) được đánh giá đầy đủ trước khi chức năng được áp dụng). Tôi sẽ sử dụng cú pháp của Standard ML, vì đây là ngôn ngữ chức năng nghiêm ngặt và phổ biến trong lịch sử. Một ứng dụng nghiêm ngặt FA (nơi F và A là hai biểu thức) có thể được trì hoãn bằng cách mã hóa nó như

Thunk (F, A)

Đối tượng này chứa một hàm và một cuộc tranh cãi được gọi là một thunk. Chúng ta có thể xác định một loại thunks:

datatype ('a, 'b) thunk = Thunk of ('a -> 'b) * 'a; 

và một chức năng để đánh giá một thunk:

fun evaluate (Thunk (f, x)) = f x; 

đẹp và dễ dàng cho đến nay. Nhưng chúng tôi đã không, trên thực tế, thực hiện đánh giá lười biếng! Những gì chúng tôi đã triển khai là đánh giá thông thường, còn được gọi là call-by-name. Sự khác biệt là nếu giá trị của thunk được sử dụng nhiều lần, nó được tính toán mỗi lần. Đánh giá lười biếng (còn được gọi là call-by-need) yêu cầu đánh giá biểu thức nhiều nhất một lần.

Bằng ngôn ngữ thuần túy, nghiêm ngặt, việc đánh giá lười biếng thực tế là không thể thực hiện được. Lý do là đánh giá một thunk sửa đổi trạng thái của hệ thống: nó đi từ đánh giá không được đánh giá. Thực hiện đánh giá lười biếng đòi hỏi một cách để thay đổi trạng thái của hệ thống.

Có một sự tinh tế ở đây: nếu ngữ nghĩa của ngôn ngữ được xác định hoàn toàn về trạng thái chấm dứt biểu thức và giá trị của biểu thức chấm dứt, thì, bằng ngôn ngữ thuần khiết, gọi theo nhu cầu và gọi theo tên không thể phân biệt được. Gọi theo giá trị (nghĩa là đánh giá chặt chẽ) có thể phân biệt được vì ít biểu thức kết thúc - gọi theo nhu cầu và gọi theo từng tên ẩn bất kỳ sự chấm dứt nào xảy ra trong một đoạn không bao giờ được đánh giá. Sự tương đương của lời gọi theo nhu cầu và gọi theo tên cho phép đánh giá lười biếng được coi là tối ưu hóa việc đánh giá theo thứ tự bình thường (có tính chất lý thuyết tốt đẹp). Nhưng trong nhiều chương trình, việc sử dụng gọi theo tên thay vì gọi theo giá trị sẽ làm tăng thời gian chạy bằng cách tính toán giá trị của cùng một biểu thức lặp đi lặp lại.

Trong một ngôn ngữ có trạng thái có thể thay đổi, việc đánh giá lười biếng có thể được biểu thị bằng cách lưu giá trị vào phần thunk khi nó được tính toán.

datatype ('a, 'b) lazy_state = Lazy of ('a -> 'b) * 'a | Value of 'a; 
type ('a, 'b) lazy_state = ('a, 'b) lazy_state ref; 
let lazy (f, x) = ref (Lazy (f, x)); 
fun force r = 
    case !r of Value y => y 
      | Lazy (f, x) => let val y = f x in r := Value y; y end; 

Mã này không phải là rất phức tạp, vì vậy ngay cả trong ML tiếng địa phương cung cấp đánh giá lười biếng như một tính năng thư viện (có thể với đường cú pháp), nó không được sử dụng tất cả những gì thường trong thực tế - thường xuyên, điểm mà tại mà giá trị sẽ là cần thiết là một vị trí đã biết trong các chương trình, và các lập trình viên chỉ sử dụng một hàm và chuyển nó cho đối số của nó tại vị trí đó.

Trong khi điều này đang đi vào lãnh thổ chủ quan, tôi sẽ nói rằng việc thực hiện đánh giá lười biếng dễ dàng hơn nhiều như thế này, hơn là thực hiện đánh giá nghiêm ngặt bằng ngôn ngữ như Haskell. Buộc đánh giá nghiêm ngặt trong Haskell về cơ bản là không thể (trừ việc gói mọi thứ vào một đơn vị trạng thái và về cơ bản là viết mã ML trong cú pháp Haskell). Tất nhiên, đánh giá nghiêm ngặt không thay đổi các giá trị được chương trình tính toán, nhưng nó có thể có tác động đáng kể đến hiệu suất (và, đặc biệt, đôi khi được đánh giá cao bởi vì nó làm cho hiệu năng dễ dự đoán hơn - dự đoán hiệu suất của Chương trình Haskell có thể rất khó).

Cơ chế đánh giá và lưu trữ này là cốt lõi của trình biên dịch Haskell thực hiện dưới mui xe. Haskell là pure², vì vậy bạn không thể thực hiện điều này bằng chính ngôn ngữ! Tuy nhiên, nó là âm thanh cho trình biên dịch để làm điều đó dưới mui xe, bởi vì điều này đặc biệt sử dụng các tác dụng phụ không phá vỡ độ tinh khiết của ngôn ngữ, do đó, nó không làm mất hiệu lực bất kỳ chuyển đổi chương trình. Lý do lưu trữ giá trị của một thunk là âm thanh là nó biến đánh giá từng người một thành lời gọi theo nhu cầu, và như chúng ta đã thấy ở trên, điều này không thay đổi giá trị của biểu thức chấm dứt, cũng không thay đổi biểu thức chấm dứt.

Cách tiếp cận này có thể hơi có vấn đề với ngôn ngữ kết hợp đánh giá cục bộ hoàn toàn chức năng với môi trường đa luồng và truyền thông điệp giữa các chuỗi. (Điều này đáng chú ý là mô hình của Erlang.) Nếu một chủ đề bắt đầu đánh giá một thunk, và một sợi chỉ cần giá trị của nó chỉ sau đó, những gì sẽ xảy ra? Nếu không có biện pháp phòng ngừa được thực hiện, sau đó cả hai chủ đề sẽ tính toán giá trị và lưu trữ nó. Trong một ngôn ngữ thuần túy, điều này là vô hại theo nghĩa là cả hai luồng sẽ tính toán cùng một giá trị anyway³. Tuy nhiên điều này có thể làm tổn thương hiệu suất. Để đảm bảo rằng một thunk được đánh giá chỉ một lần, việc tính toán giá trị phải được bao bọc trong một khóa; điều này giúp với các tính toán dài được thực hiện nhiều lần nhưng làm tổn thương các phép tính ngắn chỉ được thực hiện một lần, như việc lấy và nhả một khóa mất một thời gian.

¹ _{Chức năng, không phải là nội dung chức năng của khóa học.}
² _{Hay đúng hơn, đoạn Haskell không sử dụng một đơn nguyên có hiệu ứng phụ thuần túy. Cần phải chuyển đổi giữa giá trị trễ và một giá trị được tính là nguyên tử - các luồng đồng thời phải đọc được một giá trị lười và lấy một giá trị bị trễ hoặc giá trị được tính hợp lệ, chứ không phải một số hỗn hợp của hai không phải là một đối tượng hợp lệ. Ở cấp độ bộ vi xử lý, sự chuyển đổi từ thunk trễ sang giá trị tính toán thường là một phép gán con trỏ, mà trên hầu hết các kiến ​​trúc là nguyên tử, may mắn thay.}

Answer 2

Những gì bạn đề xuất sẽ hoạt động. Chi tiết để thực hiện việc này trong Đề án có thể là found in SICP. Người ta có thể dự tính một phiên bản Haskell nghiêm ngặt, trong đó có một chức năng "lười" mà ngược lại với những gì "seq" làm trong Haskell. Tuy nhiên, việc thêm vào một ngôn ngữ giống như Haskell nghiêm ngặt sẽ yêu cầu phép thuật biên dịch bởi vì nếu không thì thunk bị ép buộc trước khi được chuyển sang "lười".

Tuy nhiên nếu ngôn ngữ của bạn có hiệu ứng không kiểm soát được thì điều này có thể bị lông, bởi vì hiệu ứng sẽ xảy ra bất cứ khi nào chức năng kèm theo của nó được đánh giá và tìm ra khi nào điều đó xảy ra trong một ngôn ngữ lười. Đó là lý do tại sao Haskell có đơn nguyên IO.

Answer 3

đánh giá Lazy, ở mức độ thấp, được thực hiện bởi một khái niệm gọi là thunk, trong đó bao gồm hai yếu tố:

1. Một đóng cửa mà tính giá trị của việc tính toán thu nhập hoãn lại
2. Một set- một khi ô lưu trữ có thể thay đổi để ghi nhớ kết quả.

Phần đầu tiên, việc đóng, có thể được mô hình hóa theo cách đơn giản hơn so với bộ dữ liệu của bạn với hàm và đối số của nó. Bạn chỉ có thể sử dụng một hàm chấp nhận đơn vị hoặc không có đối số (tùy thuộc vào cách ngôn ngữ của bạn hoạt động), và trong phần thân của nó, bạn áp dụng hàm này cho các đối số. Để tính toán kết quả, bạn chỉ cần gọi hàm.

Paul Johnson đề cập đến Đề án, là ngôn ngữ hoàn hảo để chứng minh điều này. Là macro lược đồ (mã giả, chưa được kiểm tra):

(define-syntax delay 
    (syntax-rules() 
    ((delay expr ...) 
    ;; `(delay expr)` evaluates to a lambda that closes over 
    ;; two variables—one to store the result, one to record 
    ;; whether the thunk has been forced. 
    (let ((value #f) 
      (done? #f)) 
     (lambda() 
     (unless done? 
      (set! value (begin expr ...)) 
      (set! done? #t)) 
     value))))) 

(define (force thunk) 
    ;; Thunks are procedures, so to force them you just invoke them. 
    (thunk)) 

Nhưng để lấy lại tiêu đề câu hỏi: điều này có nghĩa là mọi ngôn ngữ chức năng đều có thể lười không? Câu trả lời là no. Ngôn ngữ mong muốn có thể triển khai thực hiện và sử dụng nó để cung cấp đánh giá bị trì hoãn chọn tham gia tại các điểm được người dùng chọn, nhưng điều này không giống như việc đánh giá lười biếng phổ biến như triển khai Haskell cung cấp.