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

 (github.com/ArhanChaudhary)
2 điểm bởi GN⁺ 2024-04-27 | 1 bình luận | Chia sẻ qua WhatsApp
  • NAND là máy tính 16-bit tương đương Turing được mô phỏng trên web, dựa trên tiền đề giáo dục rằng nó chỉ được cấu thành từ clock và cổng NAND, bao gồm từ CPU đến IDE và UI
  • Stack riêng của nó dựa trên nền tảng Jack-VM-Hack, đồng thời cung cấp CPU, ngôn ngữ máy, assembly, assembler, ngôn ngữ VM, VM translator, ngôn ngữ Jack và compiler
  • Các chương trình ví dụ không chỉ gồm Average, Pong, 2048 mà còn có demo VM escape dùng stack overflow và stack smashing, cùng GeneticAlgorithm sử dụng machine learning đơn giản
  • Jack là ngôn ngữ hướng đối tượng kiểu yếu có cú pháp gần giống Java, nhưng về nội bộ chỉ dựa vào một signed 16-bit integer, với nhiều hạn chế như không có độ ưu tiên toán tử, quản lý bộ nhớ thủ công và hành vi không được xác định
  • Dự án không có nghĩa là mọi phép tính thực sự đều chạy trên các cổng NAND vật lý, mà là một triển khai phục vụ giáo dục và lý thuyết dùng TypeScript compiler và VM translator, trình mô phỏng logic cổng NAND viết bằng Rust, cùng WebAssembly

Toàn bộ stack máy tính mà NAND cung cấp

  • NAND là máy tính 16-bit chạy trên web, được giới thiệu là viết tắt của Not A Nand-powered Device
  • Nó mô phỏng một máy tính tương đương Turing được tạo từ clock và cổng NAND, đồng thời tự tích hợp các thành phần sau
    • CPU
    • ngôn ngữ mã máy
    • ngôn ngữ assembly
    • assembler
    • ngôn ngữ máy ảo
    • VM translator
    • ngôn ngữ lập trình
    • compiler
    • IDE
    • giao diện người dùng
  • Nền tảng của nó là nền tảng Jack-VM-Hack từ khóa học Nand to Tetris và các đầu sách liên quan
  • Có cung cấp video demo NAND

Chương trình mẫu và demo

  • Average

    • Chương trình đơn giản thực hiện nhập số và tính giá trị trung bình
    • Thể hiện control flow, phép toán số học, I/O và cấp phát bộ nhớ động
    • Đây là chương trình được cung cấp trong bộ phần mềm Nand to Tetris

  • Pong

    • Trò chơi Pong thể hiện mô hình hướng đối tượng
    • Dùng phím mũi tên để di chuyển paddle sang trái và phải, hất bóng
    • Mỗi lần bóng bật lại thì paddle sẽ nhỏ đi, và trò chơi kết thúc khi bóng chạm cạnh dưới màn hình
    • Đây là chương trình được cung cấp trong bộ phần mềm Nand to Tetris

  • 2048

    • Trò chơi 2048 thể hiện recursion và logic ứng dụng phức tạp
    • Trên lưới 4x4, dùng phím mũi tên để di chuyển các số, các số giống nhau sẽ được gộp lại
    • Khi đạt tile 2048 thì thắng, nhưng vẫn có thể tiếp tục chơi cho đến lúc thua

  • Overflow

    • Cố tình gây ra stack overflow bằng đệ quy vô hạn để thực hiện virtual machine escape
    • Khai thác việc runtime không có kiểm tra ngăn stack overflow
    • Khi giá trị stack pointer vượt quá 2048, stack sẽ đi ra ngoài vùng bộ nhớ được dự kiến và tràn vào vùng bộ nhớ heap
    • Nếu chạy trên RAM trống, chương trình có thể bị reset giữa chừng do instruction đặt program counter về 0
    • Nếu chạy ngay sau GeneticAlgorithm, nó có thể đọc lại dữ liệu RAM cũ chưa bị ghi đè

  • SecretPassword

    • Lợi dụng việc runtime không ngăn stack smashing để gọi một hàm vốn không thể truy cập
    • Người dùng có thể ghi đè một địa chỉ bộ nhớ trong RAM bằng giá trị mong muốn
    • Nếu ghi đè return address của stack frame bằng địa chỉ của hàm khác, có thể thực thi mã tùy ý trong chương trình
    • Giá trị ví dụ là memory location 267, overwrite value 1743
    • Cùng loại lỗ hổng này cũng tồn tại trong buffer overflow của C

  • GeneticAlgorithm

    • Đây là mô phỏng sinh vật sử dụng machine learning đơn giản
    • Mỗi dot có “brain” riêng được cấu thành từ vector gia tốc, và tiến hóa để chạm tới goal thông qua chọn lọc tự nhiên
    • Dot chết ở vị trí càng gần goal thì càng có khả năng được chọn làm parent cho thế hệ tiếp theo
    • Trong quá trình reproduction, một phần brain sẽ bị mutation để mô phỏng tiến hóa tự nhiên
    • Có cung cấp video demo Genetic Algorithm

Các giới hạn phần cứng mà GeneticAlgorithm gặp phải

  • GeneticAlgorithm là chương trình đơn lẻ mất nhiều thời gian phát triển nhất trong số nhiều thành phần của NAND
  • Vì hiệu năng, yếu tố duy nhất mà dot dùng trong tiến hóa là mức độ gần goal tại thời điểm chết, nên entropy của thuật toán chọn lọc tự nhiên thấp
  • Vì mức dùng bộ nhớ, số lượng dot và kích thước brain bị giới hạn ở mức chưa thật sự thỏa đáng
  • Do độ phức tạp kỹ thuật, ngay cả khi đặt lại obstacle trong lúc mô phỏng cũng không thể bảo đảm brain của dot đủ lớn để tới được goal
    • Kích thước brain chỉ được quyết định tại thời điểm khởi động chương trình
  • Phần triển khai đã vượt qua các ràng buộc của NAND bằng nhiều tối ưu hóa
    • Không gian bộ nhớ lệnh ROM bị giới hạn, nên nếu mã quá nhiều thì sẽ không thể compile
    • GeneticAlgorithm cuối cùng sử dụng 99.2% không gian bộ nhớ lệnh
    • Không gian bộ nhớ RAM bị giới hạn, nên phải tối ưu mức sử dụng bộ nhớ heap
    • Lý do màn hình bị lấp đầy tĩnh giữa các thế hệ là vì vùng bộ nhớ màn hình được dùng làm bộ nhớ hoán đổi tạm cho thế hệ tiếp theo
    • NAND không có kiểu floating point, và phạm vi integer có thể biểu diễn là từ -32768 đến 32767
    • Độ chính xác của phép tính fitness bị giảm, đồng thời cũng phải tính đến integer overflow
  • Các tối ưu hóa liên quan và insight bổ sung được ghi lại trong codebase GeneticAlgorithm

Viết chương trình NAND bằng Jack

  • Nguyên nhân quan trọng nhất khiến chương trình không chạy trong Jack là không có thứ tự ưu tiên toán tử
    • 4 * 2 + 3 phải được viết như (4 * 2) + 3
    • if (~x & y) phải được viết như if ((~x) & y)
    • Giá trị đánh giá của một expression mơ hồ không có dấu ngoặc là undefined
  • Jack là ngôn ngữ lập trình hướng đối tượng weakly typed của NAND
    • Theo mô tả, nó gần với “C có cú pháp Java” hơn
    • Vì NAND có complete tech stack riêng nên có thể chỉ lập trình bằng Jack
  • Jack OS cơ bản được bundle cùng chương trình khi compile
    • Cung cấp interface với strings, memory và hardware
    • Bao gồm các hàm như Keyboard.readLine, Keyboard.readInt, Output.printString, Output.println
  • Jack hỗ trợ ba primitive type là int, char, boolean
    • Có thể định nghĩa abstract data type thông qua class
    • Biến field khai báo attribute cho từng instance
    • Biến field có scope private, cần method để truy cập từ bên ngoài
  • function và method có cách gọi khác nhau
    • Method của object hiện tại có thể được gọi trong cùng class như do g();
    • Function call phải có thêm class name ở phía trước
    • Method của object được gọi thông qua object như do b.q();

Tính kiểu yếu và quản lý bộ nhớ trong Jack

  • Không giống Java, Jack không hỗ trợ strong type, down casting, polymorphism hay inheritance
  • Về nội bộ, thực tế chỉ có một type duy nhất là signed 16-bit integer
    • Compiler không quan tâm nếu trộn type trong assignment và operation
    • Nếu gán 65 vào char thì có thể xử lý tương đương với 'A'
    • Nếu gán 5000 vào biến Array rồi thực hiện a[100] = 77 thì sẽ thành RAM[5100] = 77
    • Phần tử array có thể chứa các data type khác nhau
    • Nếu memory layout khớp, có thể dùng Array như instance của class khác
  • Jack là ngôn ngữ quản lý bộ nhớ thủ công
    • Nếu không deallocate vùng nhớ không còn cần thiết thì sẽ xảy ra memory leak
    • Heap overflow xuất hiện dưới dạng ERR6
    • Jack OS lưu array và string trên heap chứ không phải stack
  • Best practice là class biểu diễn object nên có method dispose
    • Trước tiên gọi dispose của các biến field
    • Cuối cùng deallocate chính object instance bằng do Memory.deAlloc(this);
  • Vòng lặp liên tục tạo string literal rồi in ra có thể gây heap overflow
    • Có thể dispose string ở mỗi lần lặp
    • Hoặc chỉ allocate string một lần rồi tái sử dụng để in liên tục

Hành vi không xác định và các điểm cần lưu ý

  • Toán tử so sánh

    • a > b và a < b không phải lúc nào cũng chính xác về mặt toán học
    • VM implementation chuyển a > b thành a - b > 0
    • a - b có thể overflow nên 20000 > -20000 sẽ thành false
    • Nếu absolute distance giữa a và b lớn hơn 32767 thì > và < có thể cho kết quả sai
    • Hành vi này không được sửa vì lý do compatibility với Nand to Tetris

  • -32768

    • -32768 là giá trị duy nhất mà -(-32768) = -32768
    • Nó không có positive counterpart nên có thể tạo ra unsoundness và logic error
    • Output.printInt nội bộ kỳ vọng Math.abs sẽ trả về positive number, nhưng với -32768 thì không như vậy nên Jack OS hoạt động sai

  • Gọi hàm với quá ít đối số

    • Nếu gọi function có parameter mà không truyền đối số thì có thể phát sinh undefined behavior
    • Ngược lại, function call có quá nhiều đối số vẫn hợp lệ, và extra argument có thể được index bằng keyword arguments
    • Không có argument count indicator

  • Type casting không phù hợp

    • Có thể dùng Array để cast biến sang type khác
    • Nếu gọi instance method không tồn tại trên biến đã cast thì đó là undefined behavior
    • Compiler không đủ thông minh để phát hiện việc này

  • Chỉnh sửa stack frame và internal register

    • Nếu sửa stack frame ở memory address 256~2047 hoặc internal register ở 1~15 thì có thể phát sinh undefined behavior
    • Nói chung điều này khó xảy ra nếu không lạm dụng Memory.poke hoặc dùng negative array indexing

  • Nạp file VM của người dùng

    • NAND cung cấp program validation cho file .jack, nhưng không cung cấp cho file .vm
    • Trong file .vm có thể gọi function không tồn tại, tham chiếu biến chưa được gán, hoặc thực hiện memory operation không hợp lệ về mặt logic
    • Trong đa số trường hợp sẽ xảy ra virtual machine escape và có thể không có gì hiển thị trên màn hình

Thông số phần cứng và bố trí bộ nhớ

  • RAM của NAND gồm 32.768 word, mỗi word chứa một số nhị phân 16-bit
  • Hardware dành trước 8.192 địa chỉ bộ nhớ cho screen
    • Mỗi bit của từng địa chỉ được ánh xạ tuyến tính tới pixel tương ứng trên màn hình 512x256
    • Đánh số bit theo cách LSb 0
  • Keyboard được map vào memory address 24576
    • Phím đang được nhấn hiện tại sẽ được phản ánh tại vị trí này
    • Khuyến nghị dùng class Keyboard của Jack OS thay vì trực tiếp xử lý user input qua địa chỉ này
  • Keyboard nhận diện ASCII character và special key
    • new line = 128
    • backspace = 129
    • left/up/right/down arrow = 130~133
    • home/end/page up/page down/insert/delete/ESC = 134~140
    • F1~F12 = 141~152
  • Hardware dành trước 240 địa chỉ bộ nhớ cho static class variable, và 1.792 địa chỉ bộ nhớ cho global stack
    • Trừ khi thực hiện deep recursion, giới hạn này nhìn chung không phải vấn đề lớn

Vượt ra ngoài Jack OS để tự triển khai OS

  • Về cơ bản, Jack OS được đóng gói cùng chương trình khi biên dịch để cung cấp chuỗi, bộ nhớ và giao diện phần cứng
  • Có thể cung cấp bản triển khai OS riêng với giao diện phần cứng chuyên dụng
    • IDE xử lý file Jack OS giống hệt file chương trình thông thường
    • File OS cũng có thể bị xóa hoặc ghi đè
  • Dù dùng OS tự viết, vẫn có những hàm lõi bắt buộc phải triển khai để biên dịch
    • Sys.init: điểm vào thực tế được hardcode trong bản triển khai VM, không phải Main.main
    • Memory.alloc: bộ cấp phát bộ nhớ heap mà class constructor dùng nội bộ khi tạo object
    • String.newWithStr: constructor nội bộ dành cho string literal
    • Math.multiply: được gọi nội bộ thay cho biểu thức Jack x * y
    • Math.divide: được gọi nội bộ thay cho biểu thức Jack x / y
  • Sys.init của Jack OS được cung cấp sẽ khởi tạo memory, math, screen, output, sau đó gọi Main.main() rồi gọi Sys.halt()

Cách hoạt động bên trong của NAND

  • Máy tính NAND tuân theo kiến trúc Harvard
    • ROM là instruction memory và RAM là data memory, tách biệt nhau
    • CPU làm cho cả hai cùng hoạt động
  • CPU là một accumulator machine
    • Control flow phụ thuộc rất nhiều vào các built-in register
    • Ở đây accumulator là thanh ghi D
  • Tập lệnh của CPU chỉ có hai opcode
    • Tập lệnh tương đối đơn giản nhưng cung cấp chức năng phong phú
    • ALU được xác định bằng các biểu thức có thể tính trong một instruction
  • Compiler và virtual machine không phải là khái niệm riêng có của NAND nên chỉ được đề cập ngắn gọn
    • Một số đặc điểm cú pháp hơi lạ là hệ quả của việc giúp triển khai compiler dễ hơn
    • Compiler là recursive descent parser dựa trên ngữ pháp LL(1)
    • Compiler tạo ra VM code, và VM được dùng như một simple stack machine
    • Mỗi VM instruction được ánh xạ sang assembly và machine code
  • Có thể xem mã triển khai tại core và compiler implementation

Cốt lõi của ngôn ngữ Jack và tài liệu tham chiếu OS

  • Chương trình Jack được tạo thành từ tập hợp các class
    • Mỗi class được định nghĩa trong một file riêng
    • Cần có ít nhất một class, và một trong số đó phải là Main
    • Theo Jack OS, entry point là hàm main của class Main
  • Class có thể chứa các khai báo field, static, constructor, method, function
    • Thứ tự khai báo field và static là tùy ý
    • Thứ tự khai báo subroutine cũng là tùy ý
    • Kiểu có thể là void, int, boolean, char hoặc tên class
  • Đặc điểm cú pháp
    • Whitespace và comment bị bỏ qua
    • & và | là bitwise operator và không short-circuit
    • true, false, null lần lượt là -1, 0, 0
    • String constant không thể trực tiếp chứa newline hoặc dấu ngoặc kép, và cũng không hỗ trợ escape
    • Dấu ngoặc kép và newline được OS cung cấp qua String.doubleQuote() và String.newLine()
    • Identifier phân biệt chữ hoa chữ thường
  • Các class chính của Jack OS
    • Array: tạo và giải phóng mảng
    • Keyboard: nhập phím bấm, ký tự, dòng văn bản, số nguyên
    • Math: abs, multiply, divide, sqrt, max, min
    • Memory: peek, poke, alloc, deAlloc
    • Output: xuất ra màn hình văn bản và di chuyển con trỏ
    • Screen: vẽ pixel, đường thẳng, hình chữ nhật, hình tròn
    • String: tạo string, giải phóng, truy cập ký tự, append, chuyển đổi số nguyên
    • Sys: halt, error, wait
  • Trạng thái không hợp lệ sẽ hiển thị mã lỗi theo dạng "ERR[N]" và chấm dứt thực thi chương trình
    • ERR3: chia cho 0
    • ERR6: tràn heap
    • ERR15, ERR16: chỉ số string vượt phạm vi
    • ERR17: string đã đầy
    • ERR20: vị trí con trỏ không hợp lệ

Đây không phải dự án chỉ gồm các cổng NAND thực sự

  • FAQ thừa nhận phần mô tả và tiêu đề “everything made from NAND gates” gây hiểu lầm, nhưng được đưa ra với thiện chí
  • Compiler và virtual machine translator được viết bằng TypeScript
  • Kernel giả lập và phần cứng giả lập không đại diện nguyên vẹn cho cách máy tính thật vận hành
  • Trình mô phỏng logic cổng NAND thực sự được viết bằng Rust và chỉ chiếm một phần nhỏ của toàn bộ codebase
    • Mã Rust được biên dịch thành WebAssembly để chạy trong trình duyệt
    • Vì vậy, tiền đề rằng mọi phép tính đều chạy trên cổng NAND về thực tế bị loại bỏ
  • NAND đóng vai trò như một dự án mang tính giáo dục và lý thuyết
    • Về lý thuyết, cùng logic CPU đó vẫn có thể chạy trên hiện thân phần cứng ngoài đời thực của phần cứng giả lập
    • Một ví dụ về dự án phần cứng FPGA dựa trên nand2tetris là https://gitlab.com/x653/nand2tetris-fpga/

Phạm vi triển khai và giới hạn của IDE

  • NAND tuân theo đặc tả của khóa học Nand to Tetris và cuốn sách liên quan
  • Tác giả đã tự triển khai đặc tả CPU, assembler, virtual machine translator và compiler, rồi port nền tảng này lên web và gắn thêm IDE cùng UI riêng
  • Lý do Jack yêu cầu khai báo kiểu là để compiler xác định instance method thuộc về class nào
    • s.appendChar(33) với s được khai báo là kiểu String sẽ được chuyển thành String.appendChar(s, 33) trong quá trình biên dịch
  • IDE hy sinh trải nghiệm người dùng để đơn giản hóa việc triển khai
    • Nó dùng contenteditable và logic định vị con trỏ để hỗ trợ syntax highlighting
    • Kết quả là chậm, lỗi khá rõ rệt và nhiều keybind phổ biến không hoạt động
  • Để biên dịch và chạy code, chỉ cần nhấn “Start”
    • OS thường mất hơi ít hơn 1 giây để khởi tạo memory và thiết lập dịch vụ

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-04-27
Ý kiến trên Hacker News

  • Đây là một side project xuất sắc và README cũng thật sự rất hay. Sau khi mày mò một chút với 6502 Computer của Ben Eater (https://eater.net/), tôi đang nghĩ sẽ thử làm theo Nand to Tetris

    • Liệu có thể tạo ra một máy tính NAND-to-Tetris vật lý không? Hay đây chỉ thuần túy là một bài thực hành trong môi trường ảo?

  • Chỉ với tài liệu này thôi cũng có thể dựng được vài môn học đại học. Tài liệu được làm rất tốt

    • Đây chẳng phải chỉ là Nand2Tetris sao? Tôi đã học khóa đó rồi, nhìn qua thì có vẻ giống, bao gồm cả ngôn ngữ Jack

  • Làm thật sự rất tốt. Có thể nói là đã trực tiếp bước qua những tầng trừu tượng mà phần lớn lập trình viên sẽ không thấy trong suốt sự nghiệp của mình

  • Công việc tuyệt vời. NAND to Tetris đã giúp tôi có được công việc đầu tiên sau khi tốt nghiệp đại học

    • Tò mò là nó đã giúp như thế nào

  • Trong kỳ thi đạt chuẩn phần cứng máy tính của UC Berkeley đầu thập niên 1990, một thiết kế tương tự là bài toán trọng tâm
    Cụ thể, đề yêu cầu thiết kế từ con số không một bộ xử lý RISC pipeline dựa trên microcode chỉ bằng cổng NAND; không cần phải chế tạo thực tế, nhưng phải nộp bản thiết kế chi tiết trên giấy

  • Công trình thật sự đáng nể. Khi học khóa Nand2Tetris, tôi cũng từng muốn tạo một bản triển khai ảo tương tự
    Việc bạn thật sự làm được rất ấn tượng, và hẳn giờ bạn đã hiểu rất rõ máy tính vận hành như thế nào

    • Sáng nay tôi cũng vừa nghĩ đến một ý tưởng tương tự là mô hình hóa các linh kiện cơ bản bằng SVG
      Thật ngạc nhiên khi biết đã có người làm xong một việc còn ấn tượng hơn điều tôi tưởng tượng cả một bậc độ lớn

  • Công việc xuất sắc. Gần đây tôi cũng bắt đầu học Nand2Tetris, và muốn hoàn thành Phần 1, tức phần phần cứng của khóa học, trong vài tháng tới
    Tôi đã ghi lại tiến độ trên blog ở đây: https://gurudas.dev/blog/2024/04/13/nand-to-tetris-2024-proj...

  • Nói dối. Bạn đã dùng cổng NAND và xung clock còn gì

    • Xung clock đó cũng có thể được tạo bằng bộ dao động vòng, và bộ dao động vòng có thể được cấu thành từ một số lẻ cổng NAND mắc như cổng NOT

  • Công việc tuyệt vời. Tôi đã đánh dấu lại để sau này xem kỹ hơn
    Tôi thích NAND-to-Tetris nhưng chưa bao giờ làm đến cùng, nên rất mong được khám phá dự án này

  • Tò mò là tổng cộng có bao nhiêu cổng NAND?

    • Tôi đã xem kỹ mã nguồn, và trong mỗi chu kỳ clock, cổng NAND được dùng 3.234 lần :)