Show HN: Máy tính lập trình được tạo từ cổng NAND

NAND: máy tính 16-bit hoàn chỉnh, tương đương Turing, được hiện thực trên web

• NAND là một máy tính 16-bit tương đương Turing được mô phỏng trên web chỉ với các cổng NAND và xung nhịp
• NAND có CPU, mã máy, assembly, assembler, ngôn ngữ VM, bộ dịch VM, ngôn ngữ lập trình, compiler, IDE và UI riêng
• NAND dựa trên nền tảng Jack-VM-Hack được mô tả trong khóa học Nand to Tetris và cuốn sách liên quan

Ví dụ chương trình

Average

• Một chương trình đơn giản nhận các con số đầu vào và tính giá trị trung bình
• Minh họa luồng điều khiển, phép toán số học, I/O và cấp phát bộ nhớ động

Pong

• Trò chơi Pong dùng để minh họa mô hình hướng đối tượng của ngôn ngữ
• Dùng phím mũi tên để di chuyển thanh đỡ sang trái và phải, đánh bật quả bóng
• Mỗi lần đỡ được bóng thì thanh đỡ sẽ ngắn lại, và trò chơi kết thúc khi bóng rơi xuống dưới màn hình

2048

• Trò chơi 2048 dùng để minh họa đệ quy và logic ứng dụng phức tạp
• Dùng phím mũi tên để di chuyển các con số trên lưới 4x4
• Các số giống nhau sẽ gộp lại khi chạm nhau
• Đạt tới ô 2048 là chiến thắng, nhưng vẫn có thể tiếp tục gom cao hơn
• Trò chơi kết thúc khi bàn cờ đầy và không còn nước đi nào

Overflow

• Một chương trình cố ý gây stack overflow bằng đệ quy vô hạn để thoát khỏi máy ảo
• Tận dụng việc không có kiểm tra runtime để ngăn stack overflow
• Khi chạy, chương trình liên tục in ra giá trị con trỏ stack
• Khi stack chạm tới cuối vùng nhớ dự định và tràn sang bộ nhớ heap, câu lệnh in sẽ bắt đầu lỗi loạn một cách bùng nổ

SecretPassword

• Một chương trình gọi được hàm không thể truy cập bằng cách tận dụng việc runtime không ngăn stack smashing
• Cần hiểu bố cục stack frame của NAND
• Cho phép người dùng ghi đè một địa chỉ bộ nhớ bất kỳ bằng một giá trị tùy ý
• Nếu ghi đè địa chỉ trả về của một hàm thành địa chỉ của hàm khác, có thể thực thi mã tùy ý
• Nếu nhập đúng vị trí bộ nhớ cụ thể và giá trị cần ghi đè, lấy được bằng cách tự kiểm tra địa chỉ stack và assembler, bạn có thể thấy ý tưởng này hoạt động

GeneticAlgorithm

• Một trong rất nhiều thành phần của NAND, và cũng là phần tốn nhiều thời gian phát triển nhất
• Mô phỏng sinh vật sử dụng học máy đơn giản
• “Bộ não” của mỗi điểm là các vector gia tốc, tiến hóa qua chọn lọc tự nhiên để tiến gần mục tiêu
• Ở mỗi thế hệ, các điểm đã “chết” nhưng ở gần mục tiêu hơn có xác suất cao hơn được chọn làm bố mẹ cho thế hệ tiếp theo
• Quá trình sinh sản làm đột biến bộ não, mô phỏng tiến hóa tự nhiên một cách hiệu quả
• Do giới hạn hiệu năng, hệ thống tận dụng nhiều kỹ thuật tối ưu để vượt qua giới hạn phần cứng và biến điều này thành khả thi

Lập trình bằng Jack

• Điều quan trọng nhất khi lập trình bằng Jack là không có độ ưu tiên toán tử. Đây có thể là lý do khiến chương trình không hoạt động đúng.
• Cần dùng dấu ngoặc để chỉ rõ thứ tự ưu tiên như 4 * 2 + 3 → (4 * 2) + 3, if (~x & y) → if ((~x) & y)

Giới thiệu về Jack

• NAND tự hào có toàn bộ stack công nghệ của riêng mình
• Jack là một ngôn ngữ hướng đối tượng kiểu yếu. Nói đơn giản thì là C với cú pháp Java
• Hãy học qua một ví dụ

Kiểu dữ liệu tùy chỉnh

• Jack hỗ trợ ba kiểu cơ bản là int, char, boolean
• Có thể mở rộng chúng thành các kiểu dữ liệu trừu tượng khi cần
• Kiến thức về lập trình hướng đối tượng có thể áp dụng ngay
• Trong ví dụ, lớp Point định nghĩa một điểm trừu tượng trong không gian
• Biến field được dùng để khai báo thuộc tính theo từng thể hiện của kiểu dữ liệu
• Cung cấp các hàm method công khai để người gọi có thể cộng điểm hoặc tính khoảng cách giữa hai điểm
• Mọi biến field đều có phạm vi riêng tư mặc định. Muốn truy cập chúng thì phải cung cấp thông qua hàm method
• Theo thông lệ, lớp dữ liệu nên định nghĩa phương thức dispose
• Tham khảo cú pháp gọi function, method

Ép kiểu yếu

• Dù đã nói Jack lấy cảm hứng lớn từ Java, nó thực chất chỉ là một lớp vỏ đơn giản
• Java là ngôn ngữ kiểu mạnh và hỗ trợ các tính năng kiểu phức tạp như downcasting, đa hình, kế thừa
• Trong khi đó, Jack thực ra chỉ hỗ trợ một kiểu duy nhất là số nguyên 16-bit có dấu
• Đây là lý do chính khiến Jack là ngôn ngữ kiểu yếu
• Vì vậy compiler của Jack không quá bận tâm nếu bạn trộn các kiểu khác nhau trong phép gán và phép toán
• Jack vẫn cung cấp một mô hình hướng đối tượng mạnh mẽ và hữu dụng
• Điều này sẽ giúp bạn hiểu khi nào và bằng cách nào cần chuyển kiểu

Quản lý bộ nhớ thủ công

• Jack là ngôn ngữ quản lý bộ nhớ thủ công
• Cần cẩn thận giải phóng đúng cách phần bộ nhớ không còn cần nữa
• Nếu không, Jack OS sẽ xem như có rò rỉ bộ nhớ
• Thực hành tốt nhất là viết một phương thức dispose cho mỗi lớp để đóng gói đúng việc giải phóng tài nguyên
• Gọi phương thức này khi đối tượng không còn cần thiết nữa sẽ giúp tránh cạn bộ nhớ heap
• Nếu từng dùng các ngôn ngữ quản lý bộ nhớ thủ công khác như C thì điều này sẽ quen thuộc
• Điểm khác là Jack OS lưu mảng và chuỗi trên heap thay vì trên stack
• Xem String.dispose để biết cách viết phương thức dispose

Hành vi không xác định

Độ ưu tiên toán tử

• Quá quan trọng nên được đưa lên trước

Toán tử nhỏ hơn và lớn hơn

• Biểu thức so sánh a > b, a < b trong Jack có vẻ đơn giản nhưng không phải lúc nào cũng đúng về mặt toán học
• Máy ảo biến nó thành a - b > 0. Nhưng a - b có thể bị overflow
• 20000 > -20000 sẽ được đánh giá thế nào? 20000 - (-20000) > 0, tức -25336 > 0, nên thành false
• Nhưng 20000 > -10000 thì thành 30000 > 0, tức true
• Nếu chênh lệch trị tuyệt đối giữa a và b lớn hơn 32767 thì a > b và a < b sẽ sai. Nếu không thì vẫn ổn
• Đây không phải bug mà là sự không tương thích với Nand to Tetris. Để giữ tương thích, hành vi này sẽ không được sửa

-32768

• -32768 là con số duy nhất có tính chất đặc biệt là -(-32768) = -32768. Nó là một singleton không có cặp dương tương ứng
• Điều này có thể gây ra các lỗi logic tưởng như vô lý
• Vì toán tử -x được xử lý nội bộ thành ~(x-1)
• Nếu gán -32768 cho x thì sẽ thỏa x-1 = ~x. ~(~x) sẽ trở lại thành x
• Chuyện gì đã xảy ra? Vì NAND là máy 16-bit nên trừ 1 từ -32768 sẽ cho ra kết quả là toàn bộ bit bị đảo
• Điều quan trọng là phải xử lý các lỗi logic trong phép toán số âm
• Việc kiểm tra trường hợp -32768 và xử lý thích hợp là trách nhiệm của lập trình viên

Gọi hàm với thiếu đối số

• Một hành vi không xác định quá hiển nhiên, không cần giải thích

Ép kiểu không phù hợp

• Có thể ép một biến sang bất kỳ kiểu nào bằng Array
• Gọi một phương thức thể hiện không tồn tại sẽ dẫn tới hành vi không xác định
• Compiler không đủ thông minh để phát hiện điều này

Stack overflow

• Xem chương trình Overflow

Sửa stack frame hoặc thanh ghi nội bộ

• Việc sửa stack frame hoặc các thanh ghi nội bộ ở các địa chỉ 256~2047, 1~15 có thể gây ra hành vi không xác định
• Thông thường điều này không thể xảy ra trừ khi lạm dụng Memory.poke hoặc chỉ số mảng âm
• Xem chương trình SecretPassword

Thông số phần cứng

• Có lý do khiến điện toán 16-bit bị đào thải từ sau thập niên 1970

• So với 32-bit hay 64-bit, năng lực xử lý và dung lượng bộ nhớ của nó bị hạn chế, không đáp ứng được yêu cầu của phần mềm hiện đại

• NAND cũng không ngoại lệ

• So với MacBook 16GiB, NAND chỉ có 4KiB RAM. Tức chỉ bằng 0.00002%

• Dù vậy, nó vẫn đủ để đưa chúng ta lên Mặt Trăng

• Jack OS dành ra 14,336 địa chỉ bộ nhớ trong tổng 4KiB cho heap. Một con số cực kỳ nhỏ

• Vì vậy, ứng dụng Jack phải giải phóng bộ nhớ thật hiệu quả

• Nếu kế hoạch của bạn quá tham vọng, bạn có thể cạn heap và buộc phải viết lại hoàn toàn kiểu dữ liệu và logic

• Trong 4KiB đó, 8,192 địa chỉ bộ nhớ được dành cho màn hình

• Mỗi bit trong mỗi địa chỉ ánh xạ tuyến tính tới pixel trên màn hình 512x256. Dùng đánh số bit LSb 0

• Địa chỉ bộ nhớ 24,576 được dành cho bàn phím

• Nó phản ánh mã ASCII của phím đang được nhấn

• Tuy nhiên, không nên truy cập trực tiếp để xử lý đầu vào người dùng. Hãy dùng lớp Keyboard và các hàm liên quan do Jack OS cung cấp

• Bàn phím của NAND nhận diện ASCII và các phím đặc biệt

• 240 địa chỉ bộ nhớ được dành cho biến tĩnh của lớp, và 1,792 địa chỉ cho stack toàn cục

• Trừ khi dùng đệ quy rất sâu, giới hạn này thường không thành vấn đề

[GN⁺]

Ý kiến Hacker News

• Có thể hiểu sâu về các mức độ trừu tượng của máy tính thông qua dự án Nand to Tetris
• Bộ kit máy tính 6502 của Ben Eater cũng có giá trị giáo dục tương tự
• Dự án này có tài liệu được sắp xếp tốt đến mức có thể dùng để xây dựng nhiều môn học ở bậc đại học
• Trong kỳ thi chuẩn năng lực phần cứng máy tính của UC Berkeley vào đầu những năm 1990, cũng từng có bài yêu cầu thiết kế một bộ xử lý RISC vi mã hóa và pipeline chỉ bằng các cổng NAND theo cách tương tự
  • Khi đó không yêu cầu chế tạo thực tế, chỉ cần viết thiết kế chi tiết trên giấy
• Dự án này trông có vẻ tương tự MarquisdeGeek/gates
• Khi học khóa Nand2Tetris, tôi từng muốn làm thứ gì đó tương tự theo cách ảo, nên việc thấy nó được hiện thực hóa ngoài đời thực rất ấn tượng
  • Điều này hẳn đã cải thiện đáng kể mức độ hiểu biết về nguyên lý hoạt động của máy tính
• Có ý kiến chỉ ra rằng ngoài cổng NAND thì còn sử dụng cả xung clock
• Tôi chưa học xong Nand2Tetris, nhưng với tư cách là một người hâm mộ, tôi rất muốn tìm hiểu kỹ dự án này
• Tôi tò mò tổng cộng đã dùng bao nhiêu cổng NAND
• Xin cảm ơn vì cách tiếp cận bám sát các nguyên lý nền tảng