Chia Sẻ Khóa Học Viết Một Compiler [Khóa 5582 A]
Tổng quan:
Compiler thường được coi là một khóa học quan trọng dành cho chuyên ngành khoa học máy tính. Điều này hoàn toàn có lý – compiler là công cụ mà các lập trình viên sử dụng hàng ngày trong công việc của họ, bất kể lĩnh vực ứng dụng nào. Hơn nữa, việc triển khai một compiler liên quan đến hầu hết mọi chủ đề của khoa học máy tính, từ lý thuyết đến thực tiễn. Do đó, việc tìm hiểu thêm về cách thức hoạt động của một compiler sẽ giúp bạn trở thành một lập trình viên am hiểu hơn.
Tuy nhiên, có vẻ như việc viết một compiler không liên quan trực tiếp đến các loại lập trình thông thường bạn làm ở công ty. Điều này có lẽ đúng. Nhưng thực chất, viết một compiler là một bài tập về quản lý độ phức tạp của phần mềm (software complexity). Compiler có rất nhiều phần chuyển động, khó test và khó debug. Do đó, compiler là một sân chơi tuyệt vời để nghiên cứu các vấn đề mà các dự án phần mềm thực tế gặp phải.
Một câu chuyện có thật: Tôi từng có một cựu sinh viên ghé qua văn phòng kể về việc cậu ấy đã giúp giải quyết một sự cố lập trình nghiêm trọng liên quan đến bảo hiểm y tế. Tôi hỏi "Cậu làm thế nào vậy?". Cậu ấy trả lời, "Tôi đã sử dụng một kỹ thuật học được khi viết một compiler."
Đối tượng mục tiêu:
Khóa học này dành cho những lập trình viên có kinh nghiệm hơn, những người quan tâm đến software design, data handling, type system và các chủ đề liên quan. Không nhiều lập trình viên có cơ hội viết một compiler trừ khi họ tham gia một khóa học về lĩnh vực này khi còn là sinh viên ngành Khoa học Máy tính hoặc khi theo học chương trình sau đại học. Do đó, khóa học này có thể là một cách tốt để bổ sung những kiến thức còn thiếu. Nếu bạn đã từng học về compiler, khóa học này có thể giúp bạn áp dụng những kiến thức đã học một cách thực tế hơn.
Định dạng hướng dẫn:
Khóa học này hoàn toàn tập trung vào dự án và được trình bày theo phong cách live-coding, không sử dụng slide kiểu PowerPoint. Mục tiêu của khóa học không chỉ là học cách viết một compiler, mà còn cả cách tiếp cận vấn đề viết một compiler từ những nguyên tắc đầu tiên. Một phần của khóa học bao gồm thảo luận nhóm về phân tích vấn đề, các kỹ thuật coding, design tradeoffs, testing và các chủ đề liên quan khác. Thời gian còn lại dành cho việc coding cá nhân.
Các ví dụ coding chủ yếu được cung cấp bằng Python. Tuy nhiên, project không sử dụng bất kỳ thư viện bên thứ ba nào, các tính năng đặc thù của Python, hoặc các công cụ phụ thuộc vào Python. Do đó, bạn có thể tự do triển khai dự án bằng bất kỳ ngôn ngữ lập trình nào bạn muốn. Viết trình một compiler cũng có thể là một cách học ngôn ngữ lập trình mới đầy thử thách nếu bạn muốn chinh phục khóa học ở "hard mode".
Điều kiện tiên quyết:
Có thể bạn nghĩ mình chưa sẵn sàng viết một compiler, nhưng nếu bạn đã coding được một thời gian và nắm vững các kiến thức cơ bản về cấu trúc dữ liệu, thì đây là điều bạn hoàn toàn có thể làm được. Không có nền tảng trước về compiler, mặc dù việc nắm vững các khái niệm phổ biến trong ngôn ngữ lập trình (ví dụ: kiểu dữ liệu, function, class, scoping rule, v.v.) là rất cần thiết. Một số kiến thức về thao tác văn bản, kiến trúc máy tính (machine instruction, memory, v.v.) và kinh nghiệm sử dụng một ngôn ngữ biên dịch trước đây cũng được khuyến khích.
Chương trình học:
Khóa học được xây dựng xoay quanh mục tiêu tạo ra một ngôn ngữ lập trình nhỏ có tên là Wabbit. Wabbit là một ngôn ngữ mệnh lệnh nhỏ, kiểu tĩnh. Bạn sẽ viết một compiler có thể nhận code Wabbit và biên dịch nó thành một chương trình native executable thông qua LLVM.
Project này tập trung giải quyết các vấn đề cốt lõi sau:
1. Data model. Các chương trình máy tính cần được biểu diễn dưới dạng một cấu trúc dữ liệu phù hợp, chứ không phải là văn bản thô. Điều này thường được gọi là Abstract Syntax Tree (AST).
2. Parsing. Bạn cần phân tích cú pháp các chương trình bằng cách chuyển đổi chúng từ text sang data model. Điều này liên quan đến tokenizing text và hiểu ngữ pháp. Bạn sẽ tự viết một recursive descent parser từ đầu.
3. Program Transformation. Compiler thường thực hiện các bước transform một chương trình thành một chương trình tương đương. Ví dụ, nhiều tính năng nâng cao của ngôn ngữ lập trình có thể được triển khai bằng cách sử dụng các tính năng đơn giản hơn đã tồn tại. Tương tự, nhiều kỹ thuật tối ưu hóa compiler dựa trên các program transform.
4. Type checking. Bạn sẽ viết một static program analyzer đơn giản để kiểm tra source code xem có lỗi kiểu dữ liệu và các vấn đề ngữ nghĩa khác hay không. Nếu thời gian cho phép, chúng ta cũng có thể thảo luận một vài chủ đề nâng cao như Algebraic Type System.
5. Code generation. Bạn sẽ yêu cầu compiler generate code cho LLVM và/hoặc WebAssembly. Sau khi có nó, bạn sẽ có các chương trình chạy với tốc độ gốc tương đương với các chương trình C. Nếu còn thời gian, chúng ta sẽ thảo luận về các mục tiêu code generation khả thi khác như byte-code interpreter và virtual machine.
Điều quan trọng cần lưu ý là mục tiêu chính của khóa học là xây dựng một trực giác vững chắc hơn về cách thức hoạt động của tất cả các phần trong một compiler. Mặc dù có rất nhiều framework và công cụ hiện có có thể được sử dụng để hỗ trợ việc tạo ra một compiler "đạt chuẩn sản xuất", bạn sẽ tự tạo ra một compiler từ đầu, dựa trên các nguyên tắc cơ bản.
Những bài học thực tế:
Mặc dù bạn khó có thể viết một compiler trong công việc hàng ngày, khóa học này đề cập đến nhiều chủ đề thực tiễn có thể áp dụng ở những lĩnh vực khác. Chúng bao gồm:
Kỹ năng Text manipulation & parsing. Những kỹ năng này có thể được áp dụng cho nhiều vấn đề khác nhau như data munging, scraping, triển khai giao thức và nhiều hơn nữa.
Thao tác với cấu trúc dữ liệu phức tạp. Viết một compiler liên quan đến vô số cấu trúc dữ liệu vượt xa list hoặc map cơ bản. Bạn sẽ xây dựng trees & directed graph. Bạn cần viết code để điều hướng qua các cấu trúc dữ liệu đó - thường sử dụng các thuật toán liên quan đến đệ quy. Quản lý complexity là một thách thức và bạn có thể sẽ nảy ra ý tưởng về cách thực hiện điều đó trong các ngữ cảnh khác (ví dụ: machine learning, networking, v.v.).
Testing. Một compiler là một trong những chương trình phức tạp nhất mà bạn từng viết, bao gồm nhiều component lồng ghép và tương tác với nhau theo những cách không hề đơn giản. Việc tìm ra cách test nó là một thách thức. Do đó, bạn sẽ khám phá các khía cạnh khác nhau của unit testing, integration testing, các testing oracle, các assertion, contract và nhiều hơn nữa.
Object Oriented Programming. Một cách tiếp cận để quản lý complexity trong một compiler project là sử dụng các kỹ thuật lập trình hướng đối tượng và các design pattern khác nhau. Mặc dù lập trình hướng đối tượng không phải là trọng tâm chính, nhưng có nhiều khía cạnh của dự án mà tư duy hướng đối tượng có thể hữu ích. Vì vậy, bạn có thể xem đây là một cơ hội để thực hành.
Functional Programming. Một cách tiếp cận khác để quản lý complexity là áp dụng các ý tưởng từ functional programming. Compiler rất phù hợp với các thuật toán đệ quy, pattern matching, combinator và các kỹ thuật khác.
Programming Language Semantics. Ngôn ngữ lập trình yêu thích của bạn thực sự hoạt động như thế nào? Không, ý tôi là bạn CÓ THỰC SỰ hiểu cách nó hoạt động không? Để viết một compiler, bạn phải nắm vững rất nhiều chi tiết quan trọng, thường là chuyên sâu, và thường rất tinh tế. Ví dụ, type system cơ bản, memory management, evaluation rules, call stack, và nhiều hơn nữa. Sau khi bạn hoàn thành việc viết một compiler, bạn sẽ không bao giờ nhìn nhận một ngôn ngữ lập trình theo cách cũ nữa - bạn sẽ hiểu rõ hơn rất nhiều về mọi thứ.
Kiến thức chuyên sâu về Computing. Lần tiếp theo khi bạn tham dự một bữa tiệc và hai người sắp bước vào một cuộc tranh cãi nảy lửa về tail-call optimization, bạn sẽ có thể can thiệp và giải quyết tình huống khó xử đó. Tại sao? Bởi vì bạn đã học về compiler, đó là lý do. Bạn không cần phải là sinh viên chuyên ngành khoa học máy tính để học compiler, nhưng khi hoàn thành, bạn có thể bị nhầm là một người học chuyên ngành đó.
Bạn bị điên à?
Viết một compiler chỉ trong 5 ngày? Liệu điều đó có khả thi? Chắc chắn rồi, compiler thường được coi là một trong những môn học khó nhất trong ngành Khoa học Máy tính. Nếu bạn học môn này ở trường Đại học, bạn có thể gặp một giáo sư sẽ bắt bạn phải học qua cuốn sách Dragon Book khét tiếng, dành nhiều thời gian để chứng minh toán học (ví dụ: suy ra thuật toán LALR(1) parsing), và tập trung vào khóa học để chuẩn bị cho sinh viên tốt nghiệp nghiên cứu về ngôn ngữ lập trình trong tương lai. Đó có thể là một lớp học tuyệt vời. Tôi đã từng dạy lớp học đó. Nhưng đây KHÔNG phải là lớp học đó.
Thay vào đó, đây là khóa học về compiler dành cho các practioner. Do đó, trọng tâm chính là coding & software development. Đúng vậy, bạn sẽ học về một số khái niệm cốt lõi quan trọng làm nền tảng cho compiler. Tuy nhiên, thay vì thực hiện các chứng minh toán học liên quan đến lý thuyết parsing, chúng ta sẽ tập trung vào cách bạn thực sự triển khai một parser và thực hiện các việc như viết các unit test cho nó.
Chắc chắn rồi, bạn sẽ phải viết rất nhiều code trong khóa học này. Khóa học kéo dài hơn 40 giờ trong năm ngày. Project hoàn chỉnh cuối cùng bao gồm khoảng 2000-3000 dòng code và phức tạp không kém gì các dự án bạn thường thấy trong các khóa học về compiler ở cấp đại học dành cho sinh viên chuyên ngành khoa học máy tính. Giải pháp cuối cùng của bạn có thể sẽ có nhiều bug tương tự.