- Incremental là thư viện hỗ trợ cập nhật hiệu quả các phép tính phức tạp khi đầu vào thay đổi
- Được truyền cảm hứng từ nghiên cứu về self-adjusting computation của Umut Acar và cộng sự
- Có thể được tổ chức để các phép tính quy mô lớn như bảng tính phản ứng hiệu quả với thay đổi dữ liệu
- Có thể phản ánh dữ liệu mới vào view của ứng dụng GUI một cách hiệu quả
- Có thể đảm bảo dữ liệu dẫn xuất luôn được đồng bộ liên tục với dữ liệu gốc, như trong phép lọc hay phép biến đổi ngược của mapping
Lĩnh vực ứng dụng
- Cập nhật hiệu quả các phép tính phức tạp để đáp ứng đầu vào thay đổi
- Có thể tổ chức các phép tính quy mô lớn theo kiểu bảng tính để phản ứng với thay đổi dữ liệu
- Có thể tích hợp dữ liệu mới vào GUI view một cách hiệu quả
- Liên tục đồng bộ dữ liệu dẫn xuất được tính từ dữ liệu gốc
- Lọc dữ liệu
- Biến đổi ngược của mapping
Bối cảnh thiết kế và tài liệu
- Được truyền cảm hứng từ nghiên cứu về self-adjusting computation của Umut Acar và cộng sự
- Có thể xem API chi tiết và cách sử dụng tại incremental/src/incremental_intf.ml
- Cung cấp bài viết blog và video giới thiệu như tài liệu nhập môn không chính thức
1 bình luận
Ý kiến trên Hacker News
Kiểu lập trình phản ứng này hiện được dùng rộng rãi trong các framework UI JavaScript dưới tên signals, và một đề xuất tiêu chuẩn hóa cũng đang được thúc đẩy
Vue, SolidJS, Svelte, Ember, Angular đều sử dụng nó, còn trong React thì có các triển khai như MobX và Jotai. Cũng có nhiều thuật toán khác nhau cho truyền bá thay đổi và đánh giá đồ thị có hướng không chu trình (DAG), và tôi được biết SolidJS 2 dùng thuật toán dựa trên chiều cao tương tự Incremental
Tôi đang thử nghiệm một triển khai cấp phát node trong arena
Int32Arrayvà nối bằng danh sách liên kết để tránh gánh nặng GC tỷ lệ với số cạnh phụ thuộcRust cũng có nhiều triển khai; về framework UI có Leptos, còn về hệ thống tính toán tăng dần dùng cho mục đích chung như trong rust-analyzer thì có Salsa. Cũng có thể xem đây là hệ thống build tự động theo dõi phụ thuộc; tup đo đạc các tác vụ build để phát hiện chúng đọc file nào và thiết lập quan hệ phụ thuộc. Bài viết của tác giả và tác phẩm kinh điển Build Systems à la Carte đều đáng đọc
Tuy nhiên, tính toán tăng dần và lập trình phản ứng hàm (FRP) thực ra là hai lĩnh vực khác nhau. Tính toán tăng dần suy ra tường minh các hàm hoạt động trên delta, còn FRP cũng có thể chỉ dùng cách tìm phần bị hỏng rồi khôi phục
Thư viện Incremental có vẻ đang cố giải quyết bài toán tái cụ thể hóa từng phần đồ thị tính toán khi dữ liệu gốc thay đổi. Nó giống một hệ thống build được thiết kế tốt và là cách tiếp cận hữu ích thường thấy trong lập trình hàm
Trong lĩnh vực tính toán tăng dần còn có Differential Dataflow, Timely Dataflow là công nghệ lân cận, và DBSP. Feldera dựa trên DBSP, còn Materialize do những người liên quan tới Differential Dataflow dẫn dắt
Tôi đang phát triển modolap, một cách tiếp cận riêng chuyên cho dữ liệu và workload tài chính. Có rất nhiều bài toán lớn và quan trọng cần giải quyết. Ngoài ra, tập về hệ thống build của Signals and Threads cũng đáng tham khảo
Goldman cũng đã dùng cùng cách tiếp cận này để định giá công cụ tài chính từ khoảng 30 năm trước. Trong khoảng 13 năm làm việc ở đó, tôi nhớ đã có những cuộc thảo luận dài về Node Purpling
Khoa học máy tính đã tiến bộ, và theo tôi đây không phải cách tiếp cận bằng đồ thị, nhưng các phép tính như vi phân rất tốn kém nên cần giảm số lần chạy xuống gần mức tối thiểu lý thuyết nhất có thể. Cũng có thảo luận HN liên quan
Đoạn mô tả vấn đề hay nhất là: chỉ cần nhìn IDE nội bộ chuyên dụng là đã đủ khiến người ta tức giận đến mức không nghỉ việc, nhưng người mới lại mất thời gian lâu bất thường để làm quen, và cả sau vài tháng vẫn phải tiếp tục học những thành phần khác biệt một cách căn bản. Bản thân tôi cũng mất khoảng 2 năm rưỡi mới hiểu hoàn toàn công việc mình làm
Gần như cũng không có đào tạo hiện đại nào cho tới khi họ nhận ra cần đào tạo lại. Điều tệ nhất là việc viết code để làm UI, và nó cũng không được phê duyệt cho các dự án mới
Một trong những bài tech talk tôi thích nhất là Seven Implementations of Incremental: https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/
Vài năm trước tôi từng rất quan tâm đến lập trình dataflow, và có vẻ nhiều người đã tiếp cận bài toán này từ nhiều hướng. Nhìn thư viện này tôi lập tức nghĩ tới Javelin của Clojure
Nếu thấy thú vị thì cũng đáng xem thư viện UI Bonsai được xây trên Incremental
Các thư viện như React dùng virtual DOM để bỏ qua hiệu quả những công việc không cần thiết, nhưng việc tạo chính virtual DOM cũng tốn thời gian. Bonsai thậm chí còn tăng dần hóa cả virtual DOM, và làm việc với nó cũng rất thú vị
Tôi từng tạo thư viện UI desktop cho Revery, hiện không còn được bảo trì nữa, nhưng nó dùng một phiên bản Bonsai khá cũ
Tôi chưa hoàn toàn hiểu điều này khác thế nào với mẫu observable, nơi đầu vào phát ra giá trị mới, đi qua phép tính rồi chuyển kết quả mới cho subscriber
Chắc hẳn có tối ưu hóa như phát hiện thay đổi và dừng lan truyền khi giá trị giữ nguyên, nhưng observable cũng có thể làm được. Phần gom các thay đổi trước khi tính lại bằng
stabilizecũng thú vị, nhưng có vẻ cũng có thể triển khai bằng observableTôi tự hỏi liệu khác biệt cốt lõi có nằm ở việc tự động cấu thành đồ thị tính toán thông qua introspection nội bộ, hay còn có yếu tố nền tảng nào hơn
Khi chỉ quan sát một phần nút, không cần cụ thể hóa toàn bộ đồ thị. Bạn có thể dừng tính toán bất cứ lúc nào, để đồ thị ở trạng thái chỉ được cập nhật một phần, tiếp tục thay đổi đầu vào, rồi lại tiếp tục cụ thể hóa các nút mình quan tâm; thuật toán sẽ tự sắp xếp mọi thay đổi
Tính toán gia tăng về bản chất là thuật ngữ bao trùm các đặc tính như vậy, và cũng có thể xây dựng cùng một hệ thống theo mô hình observer/subscriber. Bảng tính Excel cổ điển là một ví dụ hay, và bài giải thích thuật toán Salsa cũng đáng tham khảo
Bài nói chuyện của Ron Minsky rất hay
Có thể hình dung một đồ thị con hình kim cương, tách ra thành hàng trăm nút trung gian rồi lại hợp lại qua các đường đi có độ dài khác nhau. Trên một số đường có
min(A, B), và chỉ phía có giá trị lớn hơn thay đổiCách observer đơn giản có thể khiến lượng tính toán bùng nổ tới mức tiềm tàng theo hàm mũ, đồng thời dễ gây ra vấn đề đồng thời. Thư viện này vẫn gần tối ưu và chính xác ngay cả khi cấu trúc đồ thị thay đổi động. Bạn cũng có thể đạt kết quả tương tự bằng observer v.v., nhưng sẽ khó hơn nhiều để triển khai đúng mà vẫn tránh được vực thẳm hiệu năng
Điểm mạnh của các dự án Jane Street là họ đóng gói những ý tưởng vốn nằm trong nghiên cứu hoặc các hệ thống ngách thành hình thức mà lập trình viên có thể thực sự sử dụng. Dù không đưa thư viện vào dùng, tài liệu thiết kế của họ nhìn chung vẫn rất đáng đọc
Electric Clojure cung cấp rendering gia tăng vượt qua ranh giới client-server. Tôi cho rằng thứ gần nhất là SolidJS, nhưng SolidJS chỉ áp dụng cho frontend
Trước đây tôi từng làm thứ gì đó tương tự mà hầu như không tìm được tiền lệ nào. Sau đó mục đích sử dụng biến mất nên tôi đóng dự án, nhưng vẫn muốn xem lại, và nó vẫn còn trên npm với tên
data-ramblerÝ tưởng là đưa các luồng dữ liệu vào một ngôn ngữ đặc thù miền (DSL) có thể nạp vào runtime JavaScript. Mô-đun sẽ biến đổi dữ liệu thành nhiều luồng đầu ra, rồi chuyển chúng sang một thư viện báo cáo riêng để tạo báo cáo động dựa trên template
Ngay từ phiên bản đầu nó đã khá mạnh, nhưng tôi cũng có kế hoạch lớn để cải tiến theo cú pháp đậm chất JavaScript hơn nhằm giảm độ phức tạp