Show HN: NAND गेट से बना प्रोग्राम करने योग्य कंप्यूटर

 (github.com/ArhanChaudhary)
2 पॉइंट द्वारा GN⁺ 2024-04-27 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • NAND वेब पर emulated एक Turing-equivalent 16-bit computer है, जो इस शैक्षिक premise पर आधारित है कि यह केवल clock और NAND gate से बना है, और इसमें CPU से लेकर IDE और UI तक शामिल हैं
  • इसका अपना stack Jack-VM-Hack platform पर आधारित है, और CPU, machine language, assembly, assembler, VM language, VM translator, Jack language और compiler साथ में देता है
  • example programs में Average, Pong, 2048 के अलावा stack overflow और stack smashing का उपयोग करने वाला VM escape demo, और simple machine learning इस्तेमाल करने वाला GeneticAlgorithm भी शामिल है
  • Jack, Java syntax जैसी weakly typed object-oriented language है, लेकिन internally यह केवल एक signed 16-bit integer पर निर्भर करती है, और operator precedence न होना, manual memory management, undefined behavior जैसी बड़ी constraints रखती है
  • project का मतलब यह नहीं है कि असल में सारी computation physical NAND gates पर चलती है; यह TypeScript compiler और VM translator, Rust-based NAND gate logic simulator, और WebAssembly का उपयोग करने वाला educational/theoretical implementation है

NAND द्वारा दिया जाने वाला पूरा computer stack

  • NAND को Not A Nand-powered Device के संक्षेप के रूप में पेश किया गया web-based 16-bit computer है
  • यह clock और NAND gate से बने Turing-equivalent computer को emulate करता है, और अपने अंदर ये components शामिल करता है
    • CPU
    • machine code language
    • assembly language
    • assembler
    • virtual machine language
    • virtual machine translator
    • programming language
    • compiler
    • IDE
    • user interface
  • आधार Nand to Tetris course और संबंधित किताबों का Jack-VM-Hack platform है
  • NAND demo video उपलब्ध है

Example programs और demo

  • Average

    • number input और average calculation करने वाला simple program
    • control flow, arithmetic operations, I/O, dynamic memory allocation दिखाता है
    • Nand to Tetris software suite में दिया गया program है

  • Pong

    • object-oriented model दिखाने वाला Pong game
    • arrow keys से paddle को बाएँ-दाएँ move करके ball को bounce किया जाता है
    • ball हर बार bounce होने पर paddle छोटा होता जाता है, और ball screen के नीचे छूते ही game खत्म हो जाता है
    • Nand to Tetris software suite में दिया गया program है

  • 2048

    • recursion और complex application logic दिखाने वाला 2048 game
    • 4x4 grid में arrow keys से numbers move किए जाते हैं, और same numbers merge हो जाते हैं
    • 2048 tile तक पहुँचने पर जीत होती है, लेकिन हारने तक खेलना जारी रखा जा सकता है

  • Overflow

    • infinite recursion से जानबूझकर stack overflow पैदा करके virtual machine escape करता है
    • यह इस बात का फायदा उठाता है कि runtime में stack overflow prevention check नहीं है
    • stack pointer value 2048 से आगे निकलते ही stack अपने intended memory space से बाहर जाकर heap memory space में बहने लगता है
    • खाली RAM में run करने पर program counter को 0 पर set करने वाली instruction के कारण program बीच में reset हो सकता है
    • GeneticAlgorithm run के तुरंत बाद इसे run करने पर non-overwritten previous RAM memory पढ़ी जा सकती है

  • SecretPassword

    • runtime द्वारा stack smashing न रोकने का फायदा उठाकर ऐसी function call करता है जिसे normally access नहीं किया जा सकता
    • user RAM के किसी memory address को desired value से overwrite कर सकता है
    • stack frame के return address को किसी दूसरी function address से overwrite करने पर program के अंदर arbitrary code execution संभव है
    • example values memory location 267, overwrite value 1743 हैं
    • इसी तरह की vulnerability C के buffer overflow में भी मौजूद होती है

  • GeneticAlgorithm

    • simple machine learning इस्तेमाल करने वाला creature simulation है
    • हर dot के पास acceleration vector से बना अपना “brain” होता है, और natural selection के जरिए goal तक पहुँचने के लिए evolve करता है
    • goal के ज्यादा करीब position पर मरने वाले dot के next generation parent के रूप में चुने जाने की संभावना अधिक होती है
    • reproduction process में brain का कुछ हिस्सा mutate होता है और natural evolution simulate करता है
    • Genetic Algorithm demo video उपलब्ध है

GeneticAlgorithm को आई hardware constraints

  • GeneticAlgorithm, NAND के कई components में development में सबसे अधिक समय लेने वाला single program है
  • performance के कारण evolution के लिए dot जिस factor का उपयोग करता है, वह केवल मरते समय goal से उसकी दूरी है, और natural selection algorithm की entropy कम है
  • memory usage के कारण dot count और brain size पर संतोषजनक नहीं लगने वाली limits हैं
  • technical complexity के कारण simulation के दौरान obstacle को दोबारा arrange करने पर भी यह guarantee नहीं है कि dot का brain goal तक पहुँचने के लिए पर्याप्त बड़ा होगा
    • brain size केवल program शुरू होते समय decide होता है
  • implementation कई optimizations से NAND की constraints को bypass करता है
    • ROM instruction memory space सीमित है, इसलिए code बहुत ज्यादा होने पर compile नहीं होता
    • final GeneticAlgorithm instruction memory space का 99.2% उपयोग करता है
    • RAM memory space सीमित है, इसलिए heap memory usage optimize करनी पड़ती है
    • generations के बीच screen static से भर जाने की वजह यह है कि screen memory space को next generation के लिए temporary swap memory के रूप में इस्तेमाल किया जाता है
    • NAND में floating point type नहीं है, और representable integer range -32768 से 32767 तक है
    • fitness calculation की precision कम हो जाती है और integer overflow पर भी विचार करना पड़ता है
  • संबंधित optimizations और अतिरिक्त insight GeneticAlgorithm codebase में documented हैं

Jack में NAND प्रोग्राम लिखना

  • Jack में program के काम न करने की सबसे अहम वजह के तौर पर operator precedence का न होना बताया गया है
    • 4 * 2 + 3 को (4 * 2) + 3 की तरह लिखना होगा
    • if (~x & y) को if ((~x) & y) की तरह लिखना होगा
    • बिना brackets वाले ambiguous expression की evaluation value undefined होती है
  • Jack, NAND की weakly typed object-oriented programming language है
    • विवरण के हिसाब से यह “Java syntax वाला C” के ज्यादा करीब है
    • NAND का अपना complete tech stack है, इसलिए इसमें सिर्फ Jack से ही programming की जा सकती है
  • basic Jack OS compile के समय program के साथ bundle होता है
    • यह strings, memory और hardware के साथ interface देता है
    • इसमें Keyboard.readLine, Keyboard.readInt, Output.printString, Output.println जैसे functions शामिल हैं
  • Jack int, char, boolean इन तीन primitive types को support करता है
    • class के जरिए abstract data type define किया जा सकता है
    • field variable हर instance के attribute declare करता है
    • field variable का scope private होता है, और बाहर से access के लिए method चाहिए
  • function और method को call करने का तरीका अलग है
    • current object के method को उसी class के अंदर do g(); की तरह call किया जा सकता है
    • function call में class name आगे लगाना होता है
    • object method को do b.q(); की तरह object के जरिए call किया जाता है

Jack की weak typing और memory management

  • Jack, Java के उलट strong type, down casting, polymorphism, inheritance को support नहीं करता
  • internally असली type सिर्फ एक signed 16-bit integer है
    • compiler assignment और operation में types मिलाने पर ध्यान नहीं देता
    • char में 65 डालें तो उसे 'A' के बराबर treat किया जा सकता है
    • Array variable में 5000 डालकर a[100] = 77 चलाने पर RAM[5100] = 77 हो जाता है
    • array entry अलग-अलग data types रख सकती है
    • memory layout सही हो तो Array को किसी दूसरी class instance की तरह इस्तेमाल किया जा सकता है
  • Jack एक manual memory management language है
    • जिस memory की जरूरत नहीं रही उसे deallocate न करने पर memory leak होता है
    • heap overflow ERR6 के रूप में दिखता है
    • Jack OS array और string को stack में नहीं, heap में store करता है
  • object को represent करने वाली class में dispose method होना best practice है
    • field variable का dispose पहले call किया जाता है
    • आखिर में do Memory.deAlloc(this); से object instance खुद deallocate किया जाता है
  • string literal बार-बार बनाकर print करने वाला loop heap overflow करा सकता है
    • हर iteration में string को dispose करें, या
    • string को सिर्फ एक बार allocate करके reuse करें, तो लगातार print किया जा सकता है

Undefined behavior और सावधानियां

  • comparison operators

    • a > b और a < b हमेशा mathematically सही नहीं होते
    • VM implementation a > b को a - b > 0 में बदलता है
    • a - b overflow हो सकता है, इसलिए 20000 > -20000 का result false होता है
    • अगर a और b की absolute distance 32767 से ज्यादा हो, तो > और < गलत हो सकते हैं
    • Nand to Tetris के साथ compatibility की वजह से यह behavior बदला नहीं गया है

  • -32768

    • -32768 अकेली value है जिसमें -(-32768) = -32768 होता है
    • positive counterpart न होने से unsoundness और logic error हो सकते हैं
    • Output.printInt internally उम्मीद करता है कि Math.abs positive number लौटाएगा, लेकिन -32768 में ऐसा नहीं होता, इसलिए Jack OS गलत behavior करता है

  • बहुत कम arguments वाली function call

    • parameter वाले function को बिना argument call करने पर भी undefined behavior हो सकता है
    • इसके उलट, बहुत ज्यादा arguments वाली function call valid है, और extra argument को arguments keyword से index किया जा सकता है
    • argument count indicator नहीं होता

  • अनुचित type casting

    • Array का इस्तेमाल करके variable को दूसरे type में cast किया जा सकता है
    • cast किए गए variable पर ऐसी instance method call करना जो मौजूद नहीं है, undefined behavior है
    • compiler इतना smart नहीं है कि इसे पकड़ सके

  • stack frame और internal register में बदलाव

    • memory address 256~2047 के stack frame या 1~15 के internal register को modify करने पर undefined behavior हो सकता है
    • आम तौर पर कहा गया है कि Memory.poke के misuse या negative array indexing के बिना ऐसा करना मुश्किल है

  • user VM file loading

    • NAND .jack file के लिए program validation देता है, लेकिन .vm file के लिए नहीं
    • .vm file में nonexistent function call, unassigned variable reference, और logically invalid memory operation किए जा सकते हैं
    • ज्यादातर मामलों में virtual machine escape हो जाता है और screen पर कुछ भी दिखाई नहीं दे सकता

Hardware specifications और memory layout

  • NAND की RAM 32,768 words से बनी है और हर word में 16-bit binary number होता है
  • hardware, screen के लिए 8,192 memory addresses reserve करता है
    • हर address का हर bit, 512x256 screen के corresponding pixel पर linearly map होता है
    • bit numbering LSb 0 तरीके से होती है
  • keyboard memory address 24576 पर map होता है
    • अभी दबाई गई key इस location में reflect होती है
    • user input को सीधे इस address से handle करने के बजाय Jack OS की Keyboard class इस्तेमाल करने की सलाह दी जाती है
  • keyboard ASCII characters और special keys पहचानता है
    • 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 static class variable के लिए 240 memory addresses और global stack के लिए 1,792 memory addresses reserve करता है
    • कहा गया है कि जब तक deep recursion नहीं किया जाता, यह limit आम तौर पर समस्या नहीं बनती

Jack OS से आगे बढ़कर अपना OS implement करना

  • मूल रूप से Jack OS compile के समय program के साथ bundle होता है और string, memory, hardware interface उपलब्ध कराता है
  • dedicated hardware interface वाला अपना OS implementation दिया जा सकता है
    • IDE, Jack OS file को सामान्य program file की तरह ही treat करता है
    • OS file को भी delete या overwrite किया जा सकता है
  • अपना OS इस्तेमाल करने पर भी compile के लिए कुछ core functions अनिवार्य रूप से implement करने होंगे
    • Sys.init: Main.main नहीं, बल्कि VM implementation में hardcoded वास्तविक entry point है
    • Memory.alloc: class constructor जब object बनाता है, तब internally इस्तेमाल होने वाला heap memory allocator है
    • String.newWithStr: string literal के लिए internal constructor है
    • Math.multiply: Jack expression x * y की जगह internally call होता है
    • Math.divide: Jack expression x / y की जगह internally call होता है
  • दिए गए Jack OS का Sys.init memory, math, screen, output को initialize करने के बाद Main.main() call करता है और फिर Sys.halt() call करता है

NAND की अंदरूनी कार्यप्रणाली

  • NAND computer Harvard architecture का पालन करता है
    • instruction memory ROM और data memory RAM अलग-अलग होते हैं
    • CPU दोनों को साथ काम करवाता है
  • CPU एक accumulator machine है
    • control flow में built-in register पर काफी निर्भर करता है
    • यहां accumulator D register है
  • CPU instruction set में opcode केवल दो हैं
    • instruction set अपेक्षाकृत सरल है, लेकिन rich functionality देता है
    • ALU को उन expressions के रूप में specify किया जाता है जिन्हें एक instruction में calculate किया जा सकता है
  • compiler और virtual machine NAND के unique concepts नहीं हैं, इसलिए उन्हें संक्षेप में cover किया गया है
    • कुछ अजीब syntax features compiler implementation को आसान बनाने का परिणाम हैं
    • compiler LL(1) grammar पर बना recursive descent parser है
    • compiler VM code generate करता है, और VM को simple stack machine की तरह इस्तेमाल किया जाता है
    • हर VM instruction assembly और machine code में map होता है
  • implementation code core और compiler implementation में देखा जा सकता है

Jack भाषा और OS Reference की मुख्य बातें

  • Jack program class collection से बना होता है
    • class अलग file में define होती है
    • एक या अधिक classes चाहिए, और उनमें से एक Main होनी चाहिए
    • Jack OS के हिसाब से entry point Main class का main function है
  • class में field, static, constructor, method, function declarations हो सकते हैं
    • field और static declaration का क्रम arbitrary है
    • subroutine declaration का क्रम भी arbitrary है
    • type void, int, boolean, char, class name में से कोई एक होता है
  • syntax की विशेषताएं
    • whitespace और comments ignore किए जाते हैं
    • & और | bitwise operators हैं और short-circuit नहीं करते
    • true, false, null क्रमशः -1, 0, 0 हैं
    • string constant में newline या quotation mark सीधे शामिल नहीं किए जा सकते और escape भी संभव नहीं है
    • quotation mark और newline OS के String.doubleQuote() और String.newLine() से दिए जाते हैं
    • identifier case-sensitive होता है
  • Jack OS की प्रमुख classes
    • Array: array बनाना और dispose करना
    • Keyboard: key press, character, line, integer input
    • Math: abs, multiply, divide, sqrt, max, min
    • Memory: peek, poke, alloc, deAlloc
    • Output: text screen output और cursor movement
    • Screen: pixel, line, rectangle, circle drawing
    • String: string बनाना, dispose करना, character access, append, integer conversion
    • Sys: halt, error, wait
  • invalid state में "ERR[N]" format का error code दिखता है और program execution समाप्त हो जाता है
    • ERR3: division by zero
    • ERR6: heap overflow
    • ERR15, ERR16: string index out of bounds
    • ERR17: string is full
    • ERR20: illegal cursor location

यह असल NAND gates से बना project नहीं है

  • FAQ मानता है कि “everything made from NAND gates” वाला description और title misleading हैं, लेकिन good faith में हैं
  • compiler और virtual machine translator TypeScript में लिखे गए हैं
  • emulated kernel और emulated hardware, real computer के काम करने के तरीके को हूबहू represent नहीं करते
  • वास्तविक NAND gate logic simulator Rust में लिखा गया है और पूरे codebase का केवल छोटा हिस्सा है
    • Rust code browser में चलने के लिए WebAssembly में compile होता है
    • कहा गया है कि इस वजह से यह premise practically हट जाता है कि सारी computation NAND gates पर चलती है
  • NAND एक educational and theoretical project की भूमिका निभाता है
    • theoretically वही CPU logic emulated hardware के real-world manifestation में भी चल सकता है
    • nand2tetris आधारित FPGA hardware project के उदाहरण के तौर पर https://gitlab.com/x653/nand2tetris-fpga/ दिया गया है

Implementation scope और IDE की सीमाएं

  • NAND, Nand to Tetris course और संबंधित book की specification का पालन करता है
  • implementer ने CPU, assembler, virtual machine translator, compiler specification खुद implement किए, और platform को web पर port करते समय अपना IDE और UI जोड़ा
  • Jack में type explicit करना इसलिए जरूरी है ताकि compiler तय कर सके कि instance method किस class से संबंधित है
    • String type के रूप में declare किए गए s का s.appendChar(33) compile के दौरान String.appendChar(s, 33) में बदल जाता है
  • IDE implementation को simple रखने के लिए user experience की बलि देता है
    • syntax highlighting के लिए contenteditable और cursor positioning logic का इस्तेमाल करता है
    • नतीजतन यह धीमा है, साफ तौर पर buggy है, और common keybind काम नहीं करते
  • code compile और run करने के लिए “Start” दबाना होता है
    • OS आम तौर पर memory initialize और service setup में 1 second से थोड़ा कम समय लेता है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-04-27
Hacker News टिप्पणियाँ

  • शानदार side project है और README भी वाकई अच्छा है। Ben Eater के 6502 Computer(https://eater.net/) के साथ थोड़ा प्रयोग करने के बाद Nand to Tetris को follow करने का सोच रहा था

    • क्या physical NAND-to-Tetris computer बनाना भी संभव होगा? या यह सिर्फ virtual environment में किया जाने वाला अभ्यास है?

  • इस material से ही कई university courses बनाए जा सकते हैं। अच्छी तरह बनाया गया resource है

    • क्या यह बस Nand2Tetris नहीं है? मैंने वह course किया है, और पहली नज़र में यह Jack language तक शामिल करके वैसा ही लगता है

  • वाकई बहुत अच्छी तरह बनाया गया है। ज़्यादातर programmers अपने पूरे career में जिन abstraction layers को नहीं देख पाते, उन्हें इसने खुद चलकर पार किया है

  • बेहतरीन काम। NAND to Tetris ने university के बाद पहली job पाने में मेरी मदद की थी

    • जानना चाहूँगा कि इससे कैसे मदद मिली

  • 1990s की शुरुआत में UC Berkeley के computer hardware qualifying exam में ऐसा ही design मुख्य सवाल था
    खास तौर पर, सवाल था कि सिर्फ NAND gates से बिल्कुल नीचे से microcode-based pipelined RISC processor design करना; असल में बनाना ज़रूरी नहीं था, लेकिन paper पर detailed design जमा करना था

  • वाकई कमाल का काम। जब मैं Nand2Tetris course कर रहा था, तो मैं भी ऐसा ही virtual implementation बनाना चाहता था
    यह impressive है कि इसे सच में कर दिखाया, और अब इसे computer कैसे काम करता है इसकी सचमुच गहरी समझ होगी

    • मैं भी आज सुबह SVG में basic components model करने का ऐसा ही idea सोच रहा था
      लेकिन यह देखकर हैरानी हुई कि किसी ने पहले ही मेरी कल्पना से एक order of magnitude ज़्यादा शानदार काम कर दिया है

  • शानदार काम। हाल ही में मैंने भी Nand2Tetris शुरू किया है, और अगले कुछ महीनों में course के hardware part यानी Part 1 को खत्म करना चाहता हूँ
    progress यहाँ blog में लिखी है: https://gurudas.dev/blog/2024/04/13/nand-to-tetris-2024-proj...

  • झूठ है। तुमने NAND gate और clock इस्तेमाल किया है

    • वह clock भी ring oscillator से बनाई जा सकती है, और ring oscillator NAND gates को NOT gate की तरह जोड़कर odd number में लगाने से बनता है

  • शानदार काम। बाद में गहराई से देखने के लिए bookmark कर लिया है
    मुझे NAND-to-Tetris पसंद है, लेकिन मैं इसे अंत तक नहीं कर पाया, इसलिए इस project को explore करने का इंतज़ार है

  • जिज्ञासा है, कुल NAND gates की संख्या कितनी है?

    • मैंने code को ध्यान से देखा, और हर clock cycle में NAND gate 3,234 बार इस्तेमाल होता है :)