Tư duy bằng ngôn ngữ mảng
(github.com/razetime)- Lập trình K tập trung vào việc chuyển mã đã thử nghiệm trong REPL thành script, đồng thời liên tục rút gọn các mẫu mệnh lệnh lớn thành những mẫu mảng mang tính khai báo nhỏ hơn
- Script
ngn/kđược thực thi theo từng dòng giống như khi nhập trong REPL, và có thể nạp vào REPL dữ liệu cùng hàm đã lưu bằng\l file.k - Nếu bê nguyên phép nhân ma trận với ba vòng lặp kiểu Wikipedia sang, sẽ phát sinh nhiều biến toàn cục, vòng lặp lồng nhau và thao tác thay đổi trạng thái, đi ngược lại ưu điểm của K
- Quá trình cải tiến đi qua
+/fold,'each,/:eachright,\:eachleft, loại bỏ phép chuyển vị và chuyển sang dạng tacit, cô đọng từmatmul: {x{+/x*y}\:y}thànhmatmul: (+/*)\: - Ví dụ nhân ma trận cho thấy kỹ năng K nằm ở việc lặp đi lặp lại quá trình cô đọng mã, biến các thủ tục phức tạp thành biểu đạt mảng dễ đọc hơn
Luồng phát triển K lấy REPL làm trung tâm
- Toàn bộ mã nguồn có thể xem trong
matmul.ktrên GitHub - Lập trình K chủ yếu diễn ra trong REPL, rất phù hợp để thử nghiệm và cải tiến nhanh dựa trên đoạn mã trước đó
- Kết hợp
ngn/kvớirlfehỗ trợ lịch sử bằng phím mũi tên lên/xuống, đủ tốt để phát triển các chương trình K lớn hơn - Luồng làm việc tự nhiên là kiểm thử hàm trước trong REPL rồi mới chuyển vào mã thực tế
- Prettyprinting của
ngn/kluôn trả về dữ liệu K hợp lệ, nên có thể tính trước một số giá trị để tăng tốc chương trình
Mô hình thực thi script K
- Script K được chạy như thể được nhập vào REPL
- Mỗi dòng được thực thi theo thứ tự
- Nếu dòng không kết thúc bằng dấu chấm phẩy thì giá trị trả về sẽ được in ra
- Script cho phép định nghĩa nhiều dòng để tăng khả năng đọc
- Để dùng dữ liệu và hàm đã lưu trong REPL, chạy
\l file.k- Tệp sẽ được thực thi
- Dữ liệu trong tệp sẽ được nạp
- Nếu nạp cùng một tệp nhiều lần, dữ liệu trước đó sẽ bị ghi đè
- Có thể xem thêm lệnh trong phần trợ giúp REPL truy cập bằng
\
Cách rút gọn mẫu trong ngôn ngữ mảng
- K và lập trình mảng là quá trình liên tục đơn giản hóa các mẫu
- Ngay cả những mẫu lớn và khó xử lý cũng thường có một hoặc nhiều cách rút gọn thành dạng nhỏ hơn, mang tính khai báo hơn và dễ đọc hơn
- Thảo luận liên quan có thể xem chi tiết trong Patterns and Anti-patterns in APL: Escaping the Beginner's Plateau - Aaron Hsu - Dyalog '17
- Điểm khởi đầu phổ biến là cố gắng dịch các thuật toán quen thuộc từ GeeksforGeeks hoặc Wikipedia sang K
- Ví dụ ở đây dùng nhân ma trận
Khi bê nguyên nhân ma trận kiểu mệnh lệnh sang
- Matrix multiplication algorithm trên Wikipedia điền ma trận
Cbằng ba vòng lặpi,j,kvà phép cộng dồnsum - Nếu dịch trực tiếp sang K, sẽ phải gán rất nhiều giá trị toàn cục như
A,B,n,m,p,C,i,j,k,sum - Đoạn mã này dùng K như một ngôn ngữ mệnh lệnh, nên không thật sự phù hợp với thiết kế của K
- Có thể thu gọn vấn đề còn ba điểm
- Có quá nhiều gán toàn cục
- Vẫn còn nhiều tầng vòng lặp lồng nhau
- Trạng thái bị thay đổi thường xuyên
Gấp gọn từ vòng lặp trong cùng
- Vòng lặp trong cùng khởi tạo
sumbằng 0, rồi lặp quakđể cộng dồnA[i;k]*B[k;j] - Cải tiến đầu tiên là dùng fold
/để đổi phép cộng dồn thành+/- Biến toàn cục
sumbiến mất - Có thể viết gọn thành dạng
C[i;j]::+/...
- Biến toàn cục
- Tiếp theo, tận dụng việc
'each trả về một mảng để dùng trực tiếp giá trị trả về của các vòng lặp lồng nhau mà không cần thay đổiC - Sau bước này, chỉ còn ba vòng lặp không có thay đổi trạng thái, và các biến cốt lõi là
i,j,k
Quá trình loại bỏ k, j, i
- Vai trò của ba biến như sau
idùng để đánh chỉ số từng hàng củaAjdùng để đánh chỉ số từng cột củaBkdùng để đánh chỉ số từng cột củaAvà từng hàng củaB
kghép từng hàng củaAvới từng cột củaBđể nhân, nên có thể bỏ chỉ số trung gian và ghép trực tiếp- Ở bước này, bỏ được một vòng lặp và không còn cần
m
- Ở bước này, bỏ được một vòng lặp và không còn cần
- Để loại bỏ
j, cần lấy từng cột củaBvà ghép vớiA[i]- Chuyển vị
Brồi dùng eachright/:để ghép từng phần tử
- Chuyển vị
icũng có thể loại bỏ theo cách tương tự- Dùng eachleft
\:để ghép từng hàng củaAvới từng cột củaB
- Dùng eachleft
- Sau quá trình này, ta có dạng sau mà không cần biến toàn cục
matmul: {x{+/x*y}/:\:+y}
Loại bỏ chuyển vị và dạng tacit cuối cùng
- Phép chuyển vị
+có chi phí cao, nên có thể loại bỏ - Cách làm cũ là cách ngây thơ: nhân từng hàng của
xvới từng cột củay - Thay vào đó, có thể khớp từng hàng của
Bvới toàn bộAđể thực hiện cùng công việc một cách ngầm định
matmul: {x{+/x*y}\:y}
- Hàm này có thể chuyển sang dạng tacit bằng cách áp dụng quy tắc trong Chapter 3
- Kết quả cuối cùng như sau
matmul: (+/*)\:
Xây dựng trực giác ngôn ngữ mảng qua luyện tập
matmul: (+/*)\:được tinh gọn thành một hàm nhân ma trận đậm chất K- Quá trình cô đọng này lúc đầu có thể trông như có rất nhiều bước
- Càng luyện K, việc cô đọng mã càng trở nên dễ hơn và trực quan hơn
- Nhân ma trận là một thủ tục đơn giản, rất hợp với khả năng xử lý mảng của K
- Các chương sau sẽ bàn về những thuật toán không thật sự hợp với K và cách xử lý chúng
1 bình luận
Các ý kiến trên Hacker News
Thực ra, thứ cho thấy thuyết phục nhất tiềm năng của ngôn ngữ mảng là video mô tả Aaron Hsu phát triển trình biên dịch APL song song Co-dfns: https://www.youtube.com/watch?v=gcUWTa16Jc0&t=860s
Trên HN, anh ấy cũng nhiều lần viết về mật độ ngữ nghĩa dưới tên arcfide, và giải thích rằng mã APL được thiết kế để có thể nhìn thấy cách nó hoạt động, ngữ cảnh xung quanh và các phụ thuộc gần như không cần di chuyển trong phạm vi một màn hình: https://news.ycombinator.com/item?id=13571159
Quan điểm là khi mã trở nên súc tích đến mức tên thuật toán có độ dài gần tương đương với phần diễn giải chính thuật toán đó, ta sẽ đọc mã theo từng cụm thành ngữ như đọc cụm từ tiếng Anh, và việc trực tiếp sửa mọi nơi sử dụng đang thấy trên màn hình có thể nhanh hơn tạo ra trừu tượng để tái sử dụng
Nếu chưa rành lập trình mảng, tôi khuyên dùng The Array Cast làm tài liệu nhập môn: https://www.arraycast.com/episodes/
Địa chỉ RSS là https://www.arraycast.com/episodes?format=rss
map/filter/reduce gần như đã có ở khắp nơi, và tôi có cảm giác họ bỏ qua điểm rằng có thể dùng chúng mà không cần học một hệ ký hiệu mới giống chữ biểu ý
Tôi từng tiếp xúc với APL/APL2 thời thập niên 70, khi trên terminal giấy còn thực sự dùng cách in chồng ký tự, và lập tức mê nó; nhưng sau này, khi biết lập trình hàm qua ML và Haskell, tôi nhận ra thứ tôi thật sự thích ở APL không phải mảng mà là khả năng hợp thành hàm
Haskell hoàn toàn thuần khiết và kiểu được áp dụng xuyên suốt, nên ở điểm này tốt hơn nhiều, thú vị và mạnh mẽ hơn APL. Tôi đã làm nhiều dự án nhỏ và vừa, cũng tạo một prototype cho thấy có thể triển khai parser của LLVM Flang bằng parser combinator, và hằng năm giải Advent of Code chỉ với tổng cộng vài trăm dòng. Nếu thích APL thì cũng đáng thử Haskell
Giờ đây, khía cạnh “ký hiệu như công cụ tư duy” của APL với tôi trông giống như một cách hợp lý hóa sự súc tích quá mức. Nó tốt để thể hiện sức mạnh của hợp thành, nhưng cũng có thể làm hại sự rõ ràng
<=<thì đã có sẵn, và nếu dùng thứ tương ứng vớifmapthì chạy rất trơn tru|||,+++,&&&,***cũng tốt, và có thể tự tạo toán tử UTF-8 để làm cho ngắn và đẹp hơn. Chỉ tiếc là trong công việc thực tế hoặc mã Haskell nghiêm túc được công khai, hiếm khi thấy phong cách thân thiện với không gian dọc màn hình như vậyTôi thắc mắc trong các ngôn ngữ mảng, người ta thường xử lý tổng quát các bài toán kiểu “tìm mọi số nhỏ hơn N sao cho vị từ P đúng” như thế nào. Ví dụ như tìm các số nguyên tố nhỏ hơn 1000, hoặc tìm các bộ ba Pythagoras có z nhỏ hơn 1.000.000.
Nếu là ngôn ngữ mệnh lệnh thì sẽ kiểm tra vị từ trong vòng lặp, còn ngôn ngữ hàm thì dùng đệ quy hoặc map/filter trên danh sách lười, nhưng tôi hiểu rằng trong ngôn ngữ mảng, thường là tạo mảng
1..N, áp dụng vị từ để tạo mảng mặt nạ, rồi dùng mặt nạ đó để lọc mảng ban đầu.Nếu N lớn như 1 tỷ và vị từ hầu như không bao giờ đúng, việc tạo hai mảng tạm khổng lồ là mảng
1..Nvà mặt nạ trông rất lãng phí về bộ nhớ và tài nguyên. Tôi muốn biết liệu ngôn ngữ mảng có cứ tạo các mảng tạm như vậy rồi chậm đi hay không, hay phần triển khai sẽ tối ưu bằng cách nào đó như đánh giá lười.Ngược lại, các ngôn ngữ vô hướng mặc định xử lý từng giá trị một, nên lãng phí tính song song tiềm năng mà ngôn ngữ mảng khai thác bằng các thuật toán SIMD. Điều này cũng chỉ vì hiện trạng đã quen thuộc nên không mấy được nhìn nhận là vấn đề lớn, và lời giải cũng là blocking.
Trên thực tế ngôn ngữ mảng có tốt hay không còn tùy bài toán. Với phần lớn mục đích thực dụng, hiệu năng hoàn toàn không quan trọng, và danh tiếng của k có lẽ cũng đến từ việc kdb nhanh với vai trò cơ sở dữ liệu hơn là bản thân triển khai k là một ngôn ngữ nhanh. Dù vậy, chỉ cần tập trung vào các thuật toán mảng tao nhã thay vì tối ưu chi tiết theo từng máy cũng có thể nhanh đến đáng ngạc nhiên: https://mlochbaum.github.io/BQN/implementation/versusc.html
Một cách rõ ràng khác là hợp nhất vòng lặp cho toàn bộ thân chương trình để không sinh mảng tạm. Lựa chọn đơn giản hơn là chia mảng đầu vào/đầu ra thành các chunk cỡ vài chục KB để giới hạn lượng bộ nhớ tạm không cần thiết; theo tôi biết thì chưa có ngôn ngữ mảng nào tự động làm việc này, và một ngày nào đó tôi muốn thử trong CBQN. Người dùng cũng có thể làm thủ công, và nếu muốn tối đa hóa hiệu năng thì thực tế phải làm khá thường xuyên.
!10000000như một phạm vi đơn giản, chứ không thật sự tạo mảng mười triệu số nguyên.Tất nhiên, tùy dùng toán tử nào mà cuối cùng mảng như vậy vẫn có thể được tạo ra. Ngoài ra còn có tối ưu hóa đổi các mẫu như
+|x, tức đảo ngược x rồi lấy phần tử đầu tiên, thành chỉ lấy phần tử cuối cùng.Dĩ nhiên có thể viết theo cách khác để tránh, nhưng các lời giải đó có thể dài hơn và kém đẹp hơn. Phương ngữ APL Kap mà tôi đang làm việc trì hoãn tính toán cho đến khi cần kết quả, xử lý nhiều trường hợp để có thể viết mã theo cách trực quan mà vẫn không tính những kết quả sẽ bị bỏ đi.
Những điều tôi nhận ra rõ nhất khi dùng ngôn ngữ mảng, đặc biệt là k, là như sau. Động từ là thuật toán, còn trong các ngôn ngữ mệnh lệnh/hướng đối tượng, ta thường phải tự triển khai các thuật toán phổ biến như find, sort, group.
Chuỗi động từ hoặc trạng từ là hình thức hợp thành trực tiếp nhất mà tôi từng dùng, và việc hợp thành rất dễ, rất tự nhiên. Chương trình không còn giống một tập hợp câu lệnh và biểu thức, mà giống sự hợp thành của các thuật toán.
Nếu xử lý nhất quán khái niệm miền xác định và miền giá trị trong mảng, map và hàm, các lựa chọn thiết kế trở nên đơn giản hơn; còn đánh giá từ phải sang trái giúp khi đọc mã, mắt không phải nhảy qua nhảy lại.
Có thể và nên đưa mã đến dữ liệu thay vì đưa dữ liệu vào mã. Phần lớn dự án k lớn, nếu không tính chú thích, đều nằm gọn trong MTU mạng, tức 1540 byte. Điểm cộng của k là view có thể triển khai trực tiếp quan hệ hàm, và việc nạp mã nóng qua trình thông dịch cũng cho phép các ứng dụng chạy “mãi mãi”.
Ấn tượng cá nhân, thiên lệch và hạn chế của tôi sau khi giải các bài toán bằng ngôn ngữ K để chuẩn bị phỏng vấn xin việc là ngôn ngữ này cố ý khó hiểu. Nó là ngôn ngữ tốt cho câu đố và các lời giải thông minh.
Nhưng tôi nghĩ thứ dạy bạn về ngôn ngữ mảng và cách nghĩ bằng mảng chính là trải nghiệm làm việc với mảng NumPy trong Python.
Theo trải nghiệm dùng J khoảng 50 giờ, thành thật mà nói tôi thấy mô hình này quá lệch về một phía.
Tôi không biết việc nghĩ mọi vấn đề như các mảng lồng nhau có hữu ích như một công cụ tư duy hay không. Nếu có thể tự do tạo các cấu trúc dữ liệu nắm bắt tốt vấn đề, phần thuật toán có thể đơn giản đi rất nhiều.
Tôi nghĩ phải thông minh hơn mới dùng được APL/J/K. Trong các ngôn ngữ linh hoạt hơn, những cách tiếp cận có thể làm ngay thường lại không khả thi ở đây, nên bạn phải biến đổi vấn đề, và quá trình đó có thể đòi hỏi suy nghĩ nhiều hơn rất nhiều.
Ví dụ này dựa trên K, nhưng còn có một ngôn ngữ mảng khác là J: http://jsoftware.com
Trong J, nếu viết
dot =: +/ . *,P =: 2 3 4,Q =: 1 0 2,P dot Qthì sẽ trả về tích vô hướng của P và Q là 10.dot←+.×. Nhưng nếu ký pháp viết đầy đủ đã ngắn ngang một cái tên đủ ngắn, thì không nhất thiết phải đặt tên, và có khi còn phải thêm khoảng trắng quanh tên đó.dot = (sum.) . zipWith (*),p = [2, 3, 4],q = [1, 0, 2],p `dot` q.Với tôi, khác biệt chỉ có vẻ là dùng tên cho
sumvàzipWith, và việc lifting hay biến đổi cấu trúc không diễn ra “như phép màu”.dot::{+/x*y}. Dạng làP::[2 3 4],Q::[1 0 2],dot(P;Q).Nhìn ví dụ thì không hiểu điều này có ý nghĩa gì. Nó có hiệu năng tốt hơn theo cách nào đó không?
Cú pháp nhân ma trận thì ngắn hơn, nhưng có vẻ đó là vì bạn phải giữ trong đầu rất nhiều ngữ cảnh tích hợp sẵn về cách ngôn ngữ K hoạt động
Rất đáng thử dùng ngôn ngữ mảng và vọc cho đến khi hiểu được paradigm. Mã mệnh lệnh thường có thể được diễn đạt tốt hơn theo kiểu mảng, và đôi khi những hàm dài, lặt vặt cũng được đơn giản hóa đáng kể chỉ bằng các phép toán mảng, hoặc kết hợp với phong cách khác
Nếu so sánh
(+) <$> Just 1 <*> Just 2vớido x <- Just 1; y <- Just 2; Just (x + y)trong Haskell, ở mức độ phức tạp này tôi luôn thích cách đầu tiên hơn. Cách thứ hai chiếm nhiều không gian hơn nên khiến ta có cảm giác như đang có chuyện gì đó phức tạp hơn xảy raVới tác vụ phức tạp hơn, thay vì dùng dạng thứ hai, tôi muốn tách thành các hàm nhỏ để biến thể của cách thứ nhất trở nên hợp lý. Đây là sự đánh đổi từ “một số người mới bắt đầu có thể đọc nhanh” sang “những người từ mức trên người mới bắt đầu có thể đọc”
Nếu lấy “một số người mới bắt đầu có thể đọc” làm mục tiêu tối ưu, tôi cho rằng lợi ích sẽ giảm rất mạnh, nên thay vào đó tôi nhắm đến việc làm cho “người từ mức trên người mới bắt đầu” hoặc tùy trường hợp là “từ mức trung cấp trở lên” có thể đọc được
Với bất kỳ ngôn ngữ nào cũng có nhiều lý do để dùng và nhiều lý do để không dùng. Nhưng điểm cốt lõi không phải là ký pháp ngắn, độ rõ ràng tương đối, hay khả năng biên dịch thành mã nhanh, mà là liệu lập trình viên đến sau có thể sửa đổi và bảo trì đoạn mã đó để dùng thực tế hay không
Quá thường xuyên, các lập trình viên muốn phô diễn kỹ năng leet của mình mà không nghĩ đến những người tội nghiệp sẽ phải đến sau và tiếp quản đoạn mã đó. Trên thực tế, nhiều đoạn mã leet về lâu dài phải bị bỏ đi hoặc viết lại hoàn toàn để có được thứ gì đó có thể hỗ trợ lâu dài
Tôi đã mất nhiều thời gian để hiểu điều này, và sau đó cố gắng viết mã sạch, đơn giản, dễ hiểu để người khác có thể bảo trì. Quá nhiều khi mã dùng một lần lại đông cứng thành hạ tầng mặc định của tổ chức, rồi trở thành thứ không thể hiểu nổi đối với thế hệ tiếp theo