Show HN: คอมพิวเตอร์แบบตั้งโปรแกรมได้ที่สร้างด้วยประตู NAND

 (github.com/ArhanChaudhary)
2 คะแนน โดย GN⁺ 2024-04-27 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

NAND: คอมพิวเตอร์ 16 บิตที่สมบูรณ์แบบเทียบเท่า Turing ซึ่งจำลองบนเว็บ

  • NAND คือคอมพิวเตอร์ 16 บิตที่เทียบเท่า Turing ซึ่งถูกจำลองบนเว็บโดยใช้เพียงประตู NAND และสัญญาณนาฬิกาเท่านั้น
  • NAND มี CPU, ภาษาเครื่อง, ภาษาแอสเซมบลี, แอสเซมเบลอร์, ภาษา VM, VM translator, ภาษาโปรแกรม, คอมไพเลอร์, IDE และ UI ของตัวเอง
  • NAND อิงกับแพลตฟอร์ม Jack-VM-Hack ที่ระบุไว้ในคอร์ส Nand to Tetris และหนังสือที่เกี่ยวข้อง

ตัวอย่างโปรแกรม

Average

  • โปรแกรมง่าย ๆ ที่รับตัวเลขแล้วคำนวณค่าเฉลี่ย
  • แสดงให้เห็นการควบคุมลำดับการทำงาน, การคำนวณเลขคณิต, I/O และการจัดสรรหน่วยความจำแบบไดนามิก

Pong

  • เกม Pong ที่แสดงให้เห็นโมเดลเชิงวัตถุของภาษา
  • ใช้ปุ่มลูกศรเลื่อนไม้ตีไปทางซ้ายและขวาเพื่อเด้งลูกบอล
  • ทุกครั้งที่เด้ง ไม้ตีจะเล็กลง และเกมจะจบเมื่อลูกบอลตกลงใต้หน้าจอ

2048

  • เกม 2048 ที่แสดงให้เห็นการเรียกซ้ำและลอจิกแอปพลิเคชันที่ซับซ้อน
  • ใช้ปุ่มลูกศรเลื่อนตัวเลขบนกริด 4x4
  • ตัวเลขที่เหมือนกันจะถูกรวมเข้าด้วยกันเมื่อชนกัน
  • จะชนะเมื่อไปถึงไทล์ 2048 แต่ยังเล่นต่อเพื่อสะสมให้มากขึ้นได้
  • เกมจะจบเมื่อกระดานเต็มและไม่สามารถขยับได้อีก

Overflow

  • โปรแกรมที่จงใจทำให้เกิด stack overflow ด้วยการเรียกซ้ำไม่สิ้นสุดเพื่อหลบหนีออกจาก virtual machine
  • อาศัยข้อเท็จจริงที่ว่าไม่มีการตรวจสอบขณะรันไทม์เพื่อป้องกัน stack overflow
  • ระหว่างรันจะพิมพ์ค่าของ stack pointer ออกมาอย่างต่อเนื่อง
  • เมื่อสแตกไปถึงปลายพื้นที่หน่วยความจำที่ตั้งใจไว้และล้ำเข้าไปในหน่วยความจำฮีป คำสั่งพิมพ์จะเริ่มทำงานผิดพลาดอย่างรุนแรง

SecretPassword

  • โปรแกรมที่เรียกฟังก์ชันที่ปกติเข้าถึงไม่ได้ โดยอาศัยข้อเท็จจริงที่ว่ารันไทม์ไม่ได้ป้องกัน stack smashing
  • ต้องเข้าใจเลย์เอาต์ของ stack frame ของ NAND
  • อนุญาตให้ผู้ใช้เขียนทับที่อยู่หน่วยความจำใดก็ได้ด้วยค่าตามต้องการ
  • ถ้าเขียนทับ return address ของฟังก์ชันให้เป็นที่อยู่ของอีกฟังก์ชันหนึ่ง ก็จะสามารถรันโค้ดตามอำเภอใจได้
  • ถ้าป้อนตำแหน่งหน่วยความจำเฉพาะและค่าที่จะเขียนทับ ซึ่งได้มาจากการตรวจสอบที่อยู่สแตกและแอสเซมเบลอร์ด้วยตนเอง ก็จะเห็นว่าแนวคิดนี้ทำงานได้จริง

GeneticAlgorithm

  • เป็นส่วนที่ใช้เวลาพัฒนานานที่สุดในบรรดาคอมโพเนนต์มากมายของ NAND
  • การจำลองสิ่งมีชีวิตที่ใช้แมชชีนเลิร์นนิงอย่างง่าย
  • "สมอง" ของแต่ละจุดคือเวกเตอร์ความเร่ง ซึ่งวิวัฒน์ผ่านการคัดเลือกโดยธรรมชาติเพื่อไปให้ถึงเป้าหมาย
  • ในแต่ละรุ่น จุดที่ "ตาย" ใกล้เป้าหมายกว่าจะมีโอกาสถูกเลือกเป็นพ่อแม่ของรุ่นถัดไปมากกว่า
  • การสืบพันธุ์ทำให้สมองเกิดการกลายพันธุ์ และจำลองวิวัฒนาการตามธรรมชาติได้อย่างมีประสิทธิภาพ
  • เนื่องจากข้อจำกัดด้านประสิทธิภาพ จึงใช้เทคนิค optimization จำนวนมากเพื่อหลบข้อจำกัดของฮาร์ดแวร์และทำให้สิ่งนี้เป็นไปได้

การเขียนโปรแกรมด้วย Jack

  • สิ่งสำคัญที่สุดเวลาเขียนโปรแกรมด้วย Jack คือไม่มีลำดับความสำคัญของตัวดำเนินการ นี่อาจเป็นสาเหตุที่ทำให้โปรแกรมทำงานไม่ถูกต้อง
  • ต้องใส่วงเล็บเพื่อระบุลำดับความสำคัญให้ชัดเจน เช่น 4 * 2 + 3 → (4 * 2) + 3, if (~x & y) → if ((~x) & y)

แนะนำ Jack

  • NAND ภูมิใจกับเทคโนโลยีสแตกที่สร้างขึ้นเองครบทั้งชุด
  • Jack เป็นภาษาเชิงวัตถุแบบ weakly typed พูดง่าย ๆ คือภาษา C ที่มีไวยากรณ์แบบ Java
  • ลองเรียนรู้ผ่านตัวอย่างกัน

ชนิดข้อมูลแบบกำหนดเอง

  • Jack รองรับชนิดพื้นฐาน 3 แบบคือ int, char, boolean
  • และสามารถขยายต่อเป็น abstract data type ได้ตามต้องการ
  • นำความรู้ด้านการเขียนโปรแกรมเชิงวัตถุมาใช้ได้ทันที
  • จากตัวอย่าง Point class ใช้กำหนดจุดในปริภูมิแบบนามธรรม
  • ใช้ตัวแปร field เพื่อประกาศคุณสมบัติเฉพาะของแต่ละอินสแตนซ์ของชนิดข้อมูล
  • มีฟังก์ชัน method แบบสาธารณะสำหรับจัดการจุด เพื่อให้ผู้เรียกสามารถบวกจุดหรือคำนวณระยะห่างระหว่างสองจุดได้
  • ตัวแปร field ทั้งหมดมีขอบเขตเป็นแบบ private หากต้องการเข้าถึงตัวแปรเหล่านี้ต้องเปิดผ่านฟังก์ชัน method
  • โดยทั่วไป data class มักจะกำหนดเมธอด dispose
  • ดูไวยากรณ์การเรียก function, method

การแปลงชนิดแบบ weak typing

  • แม้จะบอกว่า Jack ได้แรงบันดาลใจอย่างมากจาก Java แต่จริง ๆ แล้วเป็นเพียงภาพลักษณ์ภายนอก
  • Java เป็นภาษาที่มี type system แข็งแรง และรองรับความสามารถด้านชนิดข้อมูลที่ซับซ้อน เช่น downcasting, polymorphism, inheritance
  • ในทางกลับกัน Jack รองรับจริง ๆ แค่ signed 16-bit integer เพียงชนิดเดียว
  • นี่คือเหตุผลหลักที่ทำให้ Jack เป็นภาษาแบบ weakly typed
  • ดังนั้นคอมไพเลอร์ของ Jack จึงไม่สนใจนักหากมีการปะปนชนิดข้อมูลต่างกันในการกำหนดค่าและการคำนวณ
  • ถึงอย่างนั้น Jack ก็ยังให้โมเดลเชิงวัตถุที่ทรงพลังและใช้งานได้จริง
  • การเข้าใจว่าควรแปลงชนิดเมื่อใดและอย่างไรจะช่วยได้มาก

การจัดการหน่วยความจำด้วยตนเอง

  • Jack เป็นภาษาที่ต้องจัดการหน่วยความจำด้วยตนเอง
  • ต้องระวังปลดปล่อยหน่วยความจำที่ไม่ต้องใช้อีกแล้วให้เหมาะสม
  • ไม่เช่นนั้น Jack OS จะถือว่าเกิด memory leak
  • แนวปฏิบัติที่ดีคือเขียนเมธอด dispose สำหรับแต่ละคลาสเพื่อครอบการจัดสรรและการคืนหน่วยความจำให้ถูกต้อง
  • หากเรียกเมธอดนี้เมื่อไม่ต้องการอ็อบเจ็กต์นั้นแล้ว ก็จะช่วยป้องกันปัญหาหน่วยความจำฮีปไม่พอได้
  • ถ้าเคยใช้ภาษาอื่นที่จัดการหน่วยความจำด้วยตนเองอย่าง C มาก่อน ก็จะคุ้นเคย
  • ความต่างคือ Jack OS เก็บอาร์เรย์และสตริงไว้บนฮีป ไม่ใช่บนสแตก
  • ดู String.dispose เพื่อเข้าใจวิธีเขียนเมธอด dispose

พฤติกรรมที่ไม่กำหนดแน่ชัด

ลำดับความสำคัญของตัวดำเนินการ

  • สำคัญมากจนต้องย้ายมาไว้ข้างหน้า

ตัวดำเนินการน้อยกว่าหรือมากกว่า

  • นิพจน์เปรียบเทียบ a > b, a < b ของ Jack ดูเหมือนง่าย แต่ในทางคณิตศาสตร์ไม่ได้ถูกต้องเสมอไป
  • virtual machine จะแปลงสิ่งนี้เป็น a - b > 0 แต่ a - b อาจ overflow ได้
  • แล้ว 20000 > -20000 จะถูกประเมินอย่างไร? 20000 - (-20000) > 0 กลายเป็น -25336 > 0 จึงได้ false
  • แต่ 20000 > -10000 จะเป็น 30000 > 0 จึงได้ true
  • หากผลต่างของค่าสัมบูรณ์ระหว่าง a และ b มากกว่า 32767 ค่า a > b และ a < b จะผิด ไม่เช่นนั้นถือว่าใช้ได้
  • นี่ไม่ใช่บั๊ก แต่เป็นความไม่เข้ากันกับ Nand to Tetris และจะไม่แก้พฤติกรรมนี้เพื่อคงความเข้ากันได้

-32768

  • -32768 เป็นตัวเลขเพียงตัวเดียวที่มีคุณสมบัติแปลกคือ -(-32768) = -32768 เป็น singleton ที่ไม่มีคู่บวกของตัวเอง
  • สิ่งนี้อาจทำให้เกิดข้อผิดพลาดทางลอจิกที่ดูไม่น่าเป็นไปได้
  • เพราะ -x ถูกจัดการภายในเป็น ~(x-1)
  • ถ้ากำหนด x เป็น -32768 จะได้ว่า x-1 = ~x และ ~(~x) จะเท่ากับ x
  • เกิดอะไรขึ้น? เพราะ NAND เป็นเครื่อง 16 บิต ดังนั้นเมื่อเอา 1 ออกจาก -32768 ผลลัพธ์ที่ได้จะเป็นการกลับบิตทั้งหมด
  • สิ่งสำคัญคือการรับมือข้อผิดพลาดทางลอจิกในการจัดการตัวดำเนินการลบค่าหนึ่งจำนวน
  • ผู้เขียนโปรแกรมต้องรับผิดชอบในการตรวจสอบกรณี -32768 และจัดการให้เหมาะสม

การเรียกฟังก์ชันโดยมีอาร์กิวเมนต์ไม่พอ

  • เป็นพฤติกรรมที่ไม่กำหนดแน่ชัดอย่างชัดเจนจนแทบไม่ต้องอธิบาย

การแคสต์ชนิดข้อมูลที่ไม่เหมาะสม

  • สามารถแคสต์ตัวแปรเป็น Array ให้เป็นชนิดใดก็ได้
  • หากเรียกใช้ instance method ที่ไม่มีอยู่ จะเกิดพฤติกรรมที่ไม่กำหนดแน่ชัด
  • คอมไพเลอร์ไม่ได้ฉลาดพอจะตรวจจับสิ่งนี้

Stack overflow

  • ดูโปรแกรม Overflow

การแก้ไข stack frame หรือรีจิสเตอร์ภายใน

  • หากแก้ไข stack frame หรือรีจิสเตอร์ภายในที่อยู่ในแอดเดรส 256~2047 และ 1~15 อาจทำให้เกิดพฤติกรรมที่ไม่กำหนดแน่ชัด
  • โดยปกติทำไม่ได้ เว้นแต่จะใช้ Memory.poke หรือดัชนีอาร์เรย์ติดลบผิดวิธี
  • ดูโปรแกรม SecretPassword

สเปกฮาร์ดแวร์

  • มีเหตุผลว่าทำไมการประมวลผลแบบ 16 บิตจึงเลือนหายไปหลังทศวรรษ 1970

  • เมื่อเทียบกับ 32 บิตหรือ 64 บิตแล้ว ทั้งความสามารถในการประมวลผลและความจุหน่วยความจำมีข้อจำกัด จึงไม่ตอบโจทย์ความต้องการของซอฟต์แวร์สมัยใหม่

  • NAND ก็ไม่ใช่ข้อยกเว้น

  • เมื่อเทียบกับ MacBook 16GiB แล้ว NAND มี RAM เพียง 4KiB เท่านั้น คิดเป็นแค่ 0.00002%

  • ถึงอย่างนั้นก็ยังมากพอจะพาเราไปดวงจันทร์ได้

  • Jack OS จอง 14,336 แอดเดรสหน่วยความจำจากทั้งหมด 4KiB ไว้สำหรับฮีป เป็นจำนวนที่น้อยผิดปกติ

  • เพราะอย่างนั้นจึงสำคัญมากที่แอปพลิเคชัน Jack จะต้องคืนหน่วยความจำอย่างมีประสิทธิภาพ

  • ถ้าแผนของคุณทะเยอทะยานเกินไป อาจเกิดปัญหาหน่วยความจำฮีปไม่พอจนต้องเขียนชนิดข้อมูลและลอจิกใหม่ทั้งหมด

  • จากทั้งหมด 4KiB มี 8,192 แอดเดรสหน่วยความจำที่ถูกจองไว้สำหรับหน้าจอ

  • ทุกบิตของแต่ละแอดเดรสถูกแมปแบบเชิงเส้นกับพิกเซลของหน้าจอ 512x256 โดยใช้การนับหมายเลขบิต LSb 0

  • แอดเดรสหน่วยความจำ 24,576 ถูกจองไว้สำหรับคีย์บอร์ด

  • จะสะท้อนค่าโค้ด ASCII ของปุ่มที่ถูกกด

  • แต่ไม่ควรเข้าถึงโดยตรงเพื่อจัดการอินพุตของผู้ใช้ ควรใช้คลาส Keyboard และฟังก์ชันที่เกี่ยวข้องที่ Jack OS มีให้

  • คีย์บอร์ดของ NAND รองรับทั้ง ASCII และปุ่มพิเศษ

  • มีการจองแอดเดรสหน่วยความจำไว้ 240 ตำแหน่งสำหรับตัวแปร static ของคลาส และ 1,792 ตำแหน่งสำหรับ global stack

  • ตราบใดที่ไม่มีการเรียกซ้ำลึกมากเกินไป ข้อจำกัดนี้ก็มักไม่เป็นปัญหา

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-04-27
ความคิดเห็นบน Hacker News
  • โปรเจ็กต์ Nand to Tetris ช่วยให้เข้าใจระดับชั้นของนามธรรมในคอมพิวเตอร์ได้อย่างลึกซึ้ง
  • ชุดคอมพิวเตอร์ 6502 ของ Ben Eater ก็มีคุณค่าทางการศึกษาในลักษณะคล้ายกัน
  • โปรเจ็กต์นี้มีเอกสารประกอบที่จัดทำไว้อย่างดีจนสามารถนำไปใช้ทำเป็นหลายวิชาในมหาวิทยาลัยได้
  • ในข้อสอบวัดคุณสมบัติด้านฮาร์ดแวร์คอมพิวเตอร์ของ UC Berkeley ช่วงต้นทศวรรษ 1990 ก็มีโจทย์ลักษณะคล้ายกัน คือให้ออกแบบโปรเซสเซอร์ RISC แบบไมโครโค้ดและทำงานแบบไปป์ไลน์โดยใช้เพียง NAND gate
    • ในเวลานั้นไม่ได้บังคับให้สร้างของจริง เพียงแค่ออกแบบรายละเอียดลงบนกระดาษก็พอ
  • โปรเจ็กต์นี้ดูคล้ายกับ MarquisdeGeek/gates
  • ตอนเรียนคอร์ส Nand2Tetris ก็อยากสร้างอะไรทำนองนี้ในแบบเสมือนจริง และน่าประทับใจที่มีคนลงมือทำมันขึ้นมาจริง ๆ
    • สิ่งนี้น่าจะช่วยเพิ่มความเข้าใจเกี่ยวกับหลักการทำงานของคอมพิวเตอร์ได้มาก
  • มีคนทักท้วงว่านอกจาก NAND gate แล้ว ยังมีการใช้สัญญาณนาฬิกาด้วย
  • แม้จะเรียน Nand2Tetris ไม่จบ แต่ในฐานะแฟนคนหนึ่งก็อยากเจาะดูโปรเจ็กต์นี้อย่างละเอียด
  • สงสัยว่าใช้ NAND gate ไปทั้งหมดกี่ตัว
  • ขอชื่นชมแนวทางที่ยึดมั่นในหลักการพื้นฐาน