TypeScript cũng bất ngờ khá ổn để triển khai compiler

 (matklad.github.io)
8 điểm bởi GN⁺ 2023-08-20 | 1 bình luận | Chia sẻ qua WhatsApp
  • Ngôn ngữ triển khai cho các công cụ dạng compiler theo truyền thống thường chia giữa OCaml và C++, nhưng trong các thử nghiệm ngôn ngữ nhỏ, TypeScript trở thành một lựa chọn có thể dùng nhẹ nhàng như các ngôn ngữ họ ML
  • Rust kết hợp ưu điểm của ML và C++, đồng thời cung cấp cả multithreading an toàn, nhưng vì phải mô hình hóa bố cục vật lý của dữ liệu nên có thể trở nên nặng nề đối với prototype nhỏ
  • Deno giúp bắt đầu nhanh các thử nghiệm ngôn ngữ bằng TypeScript nhờ single binary, linting/formatting tích hợp, không có bước compile, task runner và watch mode
  • Typechecker ví dụ kết hợp generic AST, tagged union, visitor và bottom-up transform để biến Expr<void> thành Expr<Type>, đồng thời đưa TypeError vào làm giá trị type nhằm giảm lỗi dây chuyền
  • TypeScript có thể là công cụ năng suất cho các hack ngôn ngữ nhỏ nhờ autocomplete, hệ thống type linh hoạt và đặc tính runtime cho phép chuyển sang cách động khi cần

Bố cục truyền thống khi chọn ngôn ngữ triển khai

  • Khi tạo công cụ dạng compiler, việc chọn ngôn ngữ triển khai thường có hai luồng lớn
    • OCaml phù hợp với các công việc xoay quanh ngôn ngữ như đặc tả hình thức hoặc ngôn ngữ đồ chơi theo sở thích
    • Ví dụ có plzoo và WebAssembly reference interpreter
  • Với công việc thiên về triển khai và cần sẵn sàng cho production, C++ thường được chọn
    • LLVM, clang, v8, HotSpot đều dựa trên C++
  • Rust chịu ảnh hưởng trực tiếp từ ML và C++, kết hợp ưu điểm của cả hai ngôn ngữ, đồng thời cung cấp các điểm mạnh riêng như multithreading an toàn
    • Tuy nhiên trên phổ, Rust nghiêng nhiều hơn về phía mức độ sẵn sàng cho production
    • Build system “cứ chạy là được” cũng hữu ích cho prototyping, nhưng đi kèm độ phức tạp bổ sung khi phải mô hình hóa bố cục vật lý của dữ liệu

Ưu điểm của cách dùng index trong Rust và gánh nặng với code nhỏ

  • Một lời khuyên phổ biến khi viết compiler bằng Rust là tránh pointer và dùng index
  • Index có nhiều ưu điểm trong codebase lớn
    • Có thể đặt side table trong module liên quan, giúp giảm coupling
    • Index là u32 và khuyến khích bố cục struct-of-arrays, có lợi cho hiệu năng
    • Dễ serialize hoặc kết nối với framework incremental compilation, làm chiến lược tính toán linh hoạt hơn
  • Nhưng trong lập trình quy mô nhỏ, bản thân cách dùng index trở nên rườm rà, và với các thử nghiệm sở thích thì gánh nặng này có thể là điểm chí mạng
  • OCaml vẫn còn cảm giác cũ kỹ, và trong bối cảnh này TypeScript được xem xét như một lựa chọn thay thế tương ứng với ML

Môi trường thử nghiệm nhanh mà Deno và TypeScript mang lại

  • deno được dùng làm môi trường khởi đầu
    • Cung cấp trải nghiệm dùng ngay với TypeScript
    • Ở OCaml đây là điểm gây khó chịu; Rust tốt hơn OCaml hay C++, nhưng Deno mang lại trải nghiệm đơn giản hơn Rust
  • Trải nghiệm phát triển của Deno rất hợp với các hack PLT nhỏ
    • Là single binary
    • Có linting và formatting tích hợp
    • Không có bước compile riêng
    • Có task runner và watch mode tích hợp
  • Bản thân TypeScript cung cấp một hệ thống type đủ linh hoạt nhưng vẫn nhẹ về mặt cú pháp

Các pattern TypeScript nhìn từ ví dụ typechecker nhỏ

  • AST bắt đầu bằng biểu thức có thông tin vị trí trong file
    • Location có file, line, column
    • Trong TypeScript, chuỗi chỉ là string, số chỉ là number, nên không cần băn khoăn phân biệt như usize và u32
  • Biểu thức tách riêng vị trí và kind, về sau generic hóa dữ liệu liên kết dưới dạng Expr<T>
    • Biểu thức ngay sau parsing có dữ liệu void
    • Biểu thức đã được typechecker xử lý có dữ liệu Type
    • Hàm type inference nhận ast.Expr<void> và trả về ast.Expr<Type>
  • TypeScript không tự động thêm hành vi runtime, nên để match union type cần tự đưa thông tin type runtime vào
    • Các field như tag: "binary", tag: "if" đảm nhận vai trò này
    • tag: "binary" nghĩa là ở runtime, giá trị đó chỉ có thể là chuỗi "binary"
  • Boolean literal và int literal có dạng gần như giống nhau nên được trừu tượng hóa thành ExprLiteral<T, V, Tag>
    • ExprBool<T> là ExprLiteral<T, boolean, "bool">
    • ExprInt<T> là ExprLiteral<T, number, "int">
  • Giá trị type được chia thành TypeBool, TypeInt, và các giá trị singleton cũng được cung cấp với cùng tên
    • TypeScript xóa hoàn toàn type, nên tên liên quan đến type và tên liên quan đến value tồn tại trong các namespace riêng
    • Có thể tận dụng đặc tính này để định nghĩa type và value cùng một tên

Visitor, transform, type lỗi và desugaring

  • switch của TypeScript là statement chứ không phải expression, nên một visitor được định nghĩa để xử lý expression kind thuận tiện hơn
    • Các method bool, int, binary, if lần lượt xử lý kind tương ứng
    • Autocomplete của editor hỗ trợ triển khai switch case và visitor
  • transform<U, V> là hàm duyệt tổng quát biến Expr<U> thành Expr<V>
    • Biến đổi được thực hiện bottom-up
    • Khi thăm node bên trong, các biểu thức con đã được biến đổi, nên type của visitor là Visitor<V, V> chứ không phải Visitor<U, V>
  • Có thể tận dụng việc TypeScript là ngôn ngữ type động để tạo một phép duyệt tổng quát hơn bằng Object.keys
    • Ngay cả trong trường hợp này vẫn có thể giữ chữ ký hàm tĩnh
    • Ví dụ không thật sự cần điều đó, nhưng vẫn có đường lui sang cách động khi cần
  • Lỗi type không được tích lũy trong một mảng bằng side effect, mà được biểu diễn bằng type TypeError
    • Type trở thành TypeBool | TypeInt | TypeError
    • TypeError có tag: "Error", location, message
    • type_equal trả về true nếu một trong hai phía là Error, để tránh lỗi dây chuyền
  • Typechecker cuối cùng kiểm tra binary và if
    • Biểu thức binary trả về lỗi "binary expression operands have different types" nếu type của toán hạng trái và phải khác nhau
    • Biểu thức if trả về lỗi "if condition is not a boolean" nếu điều kiện không phải boolean
    • Trả về lỗi "if branches have different types" nếu type của nhánh then và else khác nhau
  • Kết quả cần một mức typing nhất định nhưng autocomplete bù đắp rất nhiều, ít có cảm giác phải vật lộn với ngôn ngữ và khớp tự nhiên với hình dạng của vấn đề
  • Có thể tóm tắt ba lý do TypeScript hiệu quả như công cụ hack ngôn ngữ nhỏ
    • Deno là scripting runtime nhỏ, khép kín, mạnh và được tối ưu cho workflow phát triển hiệu quả
    • Công cụ TypeScript trong IDE hữu ích và năng suất, còn nhờ Deno thì không cần cấu hình
    • Ngôn ngữ mạnh ở cả runtime lẫn compile time, có thể biểu đạt khá tinh vi bằng type nhưng vẫn có thể chuyển sang cách động khi cần
  • Một ý tưởng bổ sung là cũng có thể desugar nhiều cú pháp đường một cách type-safe
    • Expr và ExprKind không được tham số hóa theo dữ liệu liên kết, mà được tham số hóa đệ quy theo toàn bộ ExprKind
    • ExprKindCore biểu thị tập biểu thức cơ bản
    • ExprKindSugar bao gồm các biểu thức cơ bản hoặc các biểu thức có thể desugar thành biểu thức cơ bản
    • desugar(expr: ExprSugar): ExprCore rút gọn biểu thức cú pháp đường thành biểu thức lõi
    • desugar_one(expr: ExprKindSugar<ExprCore>): ExprKindCore<ExprCore> thực hiện một bước biến đổi khi các biểu thức con đã được desugar

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-08-20
Ý kiến trên Hacker News

  • TypeScript nhìn chung là một ngôn ngữ xuất sắc, và việc hàm là một đối tượng có thể có property/method đang bị đánh giá thấp
    Có thể chạy một mảng các hàm như các lệnh, rồi sau đó gắn thêm mô tả như help, hoặc thêm trạng thái bằng closure/partial application, nên không cần vội định nghĩa các lớp kiểu Command
    Trong lập trình hướng đối tượng, việc đặt tên quá sớm thường tạo ra nhiều xung đột; tôi thấy truyền các giá trị cần thiết vào hàm tự nhiên hơn so với cấu trúc như VideoCompressor#compress()

    • Nói chính xác thì đây gần với tính năng của JavaScript hơn là TypeScript
      Các ngôn ngữ khác hỗ trợ đối tượng hoạt động như hàm được tổng hợp tại https://en.wikipedia.org/wiki/Function_object
    • Trong Go, có thể gắn method cho cả hàm, và thực tế là cho gần như bất kỳ kiểu nào
      Như handler của net/http, một struct có thể triển khai method serve, hoặc một hàm handler có thể gọi chính nó để thỏa mãn interface
      Trong Clojure, có thể gắn metadata vào var của hàm để xử lý tương tự; vì là Lisp nên gần như thứ gì cũng có thể làm bằng macro
      Ngoài ra, các kênh CSP của core/async tách biệt việc thực thi và giao tiếp, giúp tránh vấn đề “màu hàm” như callback/promise/async/await, và các lệnh có thể hoạt động như producer gửi kết quả vào kênh
    • Giao diện một phương thức của Java cũng có thể tạo hiệu ứng tương tự
      Dù tên method là gì, nó vẫn có thể được dùng trong ngữ cảnh hàm, và không cần tham chiếu đến tên method cụ thể
      Tuy nhiên, tôi không thích việc hàm có property để chứa trạng thái, khiến hành vi có thể thay đổi dù được gọi với cùng tham số. Tôi cho rằng một lợi thế lớn của lập trình hàm là thoát khỏi trạng thái kiểu hướng đối tượng
    • Python hỗ trợ tốt hướng này vì mọi thứ đều là đối tượng
    • Trong C#, hàm có giá trị trả về có thể được biểu diễn tương tự bằng Func, còn hàm không có giá trị trả về bằng Action
      Biểu thức lambda của JavaScript khá giống C#, và chữ ký hàm của TypeScript và C# cũng khá tương đồng
      Cũng có một repository nhỏ cho thấy sự tương đồng giữa JavaScript, TypeScript và C#: https://github.com/CharlieDigital/js-ts-csharp
      Ảnh chụp màn hình hiển thị cùng một logic song song bằng JS/TS/C#: https://github.com/CharlieDigital/js-ts-csharp/blob/main/js-...

  • Không quá ngạc nhiên. Rốt cuộc TypeScript cũng là một ngôn ngữ khác đã tiếp nhận khá nhiều tính năng thuộc họ ML theo cách không hề dễ dàng
    Vì không có pattern matching thật sự nên bất tiện hơn OCaml, nhưng nếu so với các ngôn ngữ như C#, Swift, Dart, Kotlin thì vẫn ở mức ổn

    • Đây là so sánh chỉ nhìn ở tầng quá cao. Cảm giác sử dụng thực tế khá khác
      TypeScript có hệ thống kiểu mạnh, nhưng thư viện chuẩn nền tảng và bản thân ngôn ngữ còn đáng tiếc, và không có pattern matching/switch expression
      Dart có mô hình đối tượng đóng nên mức độ tự do động thấp, hệ thống kiểu và biểu thức cũng yếu hơn, gần như không có cơ chế metaprogramming, nên phải dựa vào boilerplate kiểu Java và các trình sinh mã
      C# là ngôn ngữ gần nhất với các tính năng ML trong số những ngôn ngữ được nhắc tới, nhưng khác TypeScript ở chỗ không có sum type, khiến nhiều việc trở nên rườm rà hơn
    • Trước đây, trong một compiler phục vụ học tập kiểu Pascal-C viết bằng Haskell, parser combinator cho phép biểu diễn trực tiếp ngữ pháp bằng code gần giống BNF
      Ví dụ, có thể kết hợp parser nhận diện { ... } với parser khác, và định nghĩa một câu lệnh là một trong các dạng luồng điều khiển/khai báo/gán
      Xử lý danh sách và pattern matching kiểu ML rất giàu khả năng biểu đạt khi làm việc với biểu diễn trung gian
    • Khi cần pattern matching trong TypeScript, tôi hay dùng thư viện này: https://github.com/gvergnaud/ts-pattern
    • Khó có thể nói TypeScript đã lấy hầu hết các tính năng ML
      Ngay trong bài, vì switch không phải là biểu thức nên phải đi vòng qua visitor pattern, và hỗ trợ iterator của JavaScript cũng thiếu một cách kỳ lạ
      Có .map() nhưng chỉ hoạt động với mảng, không thể áp dụng trực tiếp cho iterator thông thường
    • Nếu dùng TypeScript và kotlin-js, sẽ thấy hai ngôn ngữ này khá gần nhau
      Có nhiều khác biệt, nhưng việc chuyển đổi không khó; cá nhân tôi thích Kotlin hơn nhưng vẫn dùng được cả hai
      Tôi tự hỏi sẽ thế nào nếu TypeScript thoát khỏi khả năng tương thích JavaScript và biên dịch sang WASM. Kotlin đang bổ sung compiler WASM và đã có sẵn JS transpiler; cùng một đoạn mã tải trên WASM nhỏ hơn và nhanh hơn
      JavaScript trên trình duyệt không phải là mục tiêu biên dịch tốt, và khi ngày càng nhiều dự án mới bắt đầu ngay bằng TypeScript, lý do phải dễ dàng chuyển đổi từ JavaScript hiện có cũng dần yếu đi

  • Khi qua lại giữa Rust và TypeScript, việc thiếu các tính năng như enum có tag hiện ra rất rõ
    Đề xuất ADT enum có vẻ đã dừng lại, không biết có nỗ lực nào khác không: https://github.com/Jack-Works/proposal-enum/discussions/19

    • Với mục đích tương tự, tôi thấy discriminated union hoạt động khá ổn

  • Hệ thống kiểu của TypeScript khá thú vị, nhưng tôi lại tò mò không biết nó sẽ nhanh hơn đến mức nào nếu trình biên dịch được viết bằng một ngôn ngữ biên dịch
    Tất nhiên, điều này cần một tiền đề lớn là “triển khai tốt”

    • swc và esbuild không phải là đối tượng so sánh tốt. Phần lớn mức tăng tốc là vì chúng loại bỏ cú pháp dành riêng cho TypeScript để tạo ra JavaScript
      tsc thường chỉ chậm ở lần chạy đầu tiên; nếu dùng cờ incremental hoặc chế độ theo dõi --transpile-only, thời gian biên dịch thường xuống dưới 100ms, nên gần như không còn khác biệt đáng kể so với SWC hay ESBuild
    • Nhóm TypeScript có trả lời về việc này: https://twitter.com/drosenwasser/status/1260723846534979584
      Ý là nếu việc kiểm tra kiểu cho một chương trình cỡ trung mất 20 giây, thì thường không phải vì nó là JS, mà vì các kiểu gây ra bùng nổ tổ hợp
      Runtime khác có thể đem lại lợi ích về tính song song hoặc thời gian khởi động, nhưng họ nói chưa thấy benchmark thiên về CPU nào chứng minh được mức tăng tốc tổng thể 20 lần
    • Hệ thống kiểu rất thú vị cho đến khi bạn tận dụng tối đa nó với generic
      Rồi sau khi debug 5 dòng logic kiểu cả ngày, bạn sẽ tự hỏi rốt cuộc mình đã đi đến đây bằng cách nào
    • Không cần chỉ tưởng tượng nữa: https://github.com/dudykr/stc
      Đây là dự án do một trong các nhà phát triển chính của SWC viết bằng Rust; SWC biên dịch TS sang JS, còn STC kiểm tra kiểu TS
    • Hiệu năng của trình biên dịch TypeScript gần đây đã cải thiện rất nhiều
      isolated declaration mode sắp tới được cho là có thể giảm thời gian biên dịch tới 75%: https://github.com/microsoft/TypeScript/pull/53463#issuecomm...

  • Với người mới bắt đầu học về trình biên dịch, tôi khuyên đọc cuốn sách này: https://keleshev.com/compiling-to-assembly-from-scratch/
    Tác giả xây dựng một trình biên dịch sang assembly ARM 32-bit bằng một tập con của TypeScript, và giải thích rằng nó trông gần như mã giả nên rất dễ tiếp cận

    • Crafting Interpreters cũng rất đáng khuyên đọc: https://craftinginterpreters.com/
      Cuốn sách được chia làm hai phần: phần đầu xây dựng một trình thông dịch ngôn ngữ bằng Java, phần hai biên dịch cùng ngôn ngữ đó thành bytecode rồi triển khai máy ảo bytecode bằng C
      Mọi dòng mã trong phần triển khai đều được tham chiếu trong sách

  • Nếu muốn tránh visitor pattern, có thể dùng hàm tiện ích run để viết switch kiểu IIFE
    Chỉ cần dùng switch bên trong một hàm gọi ngay và để nó suy luận kiểu trả về

    • Tôi từng viết về pattern này: https://maxgreenwald.me/blog/do-more-with-run
    • Thực ra đến mức đó cũng không cần; chỉ cần gọi hàm ngay thì kiểu trả về sẽ được suy luận
      Nếu không thích IIFE vì ghét phần () ở cuối, bạn có thể định nghĩa hàm riêng rồi gọi nó

  • Tôi đang viết một trình biên dịch bằng TypeScript và đồng ý rằng nó không tệ như tưởng tượng
    Ban đầu tôi cũng bắt đầu với Deno như tác giả, nhưng cuối cùng chuyển sang Bun; dù vẫn còn vài chỗ thô ráp, tôi hài lòng với nó hơn Deno và nó rất nhanh
    Với frontend sinh parser chuẩn, Ohm-js khá dễ chịu: https://ohmjs.org/
    Trình biên dịch tsc chính thức quá đồ sộ nên tôi không khuyên đọc; nếu muốn xem tsc hoạt động thế nào thì mini-typescript phù hợp hơn: https://github.com/sandersn/mini-typescript/
    Đặc biệt nhánh centi-typescript rất hữu ích: https://github.com/sandersn/mini-typescript/tree/centi-types...
    Tôi kỳ vọng GC và khả năng truy cập DOM sẽ khả dụng trong WASM

    • Tôi tò mò lý do bạn chuyển sang Bun

  • Tôi tưởng TypeScript sẽ có thêm chi phí do interface, nên kết quả này khá bất ngờ
    Tôi tự hỏi liệu có thể áp dụng cho các lĩnh vực khác không, ví dụ phân tích cú pháp ngôn ngữ thì có ổn không

    • Ở runtime, chi phí của interface là 0
      Chúng biến mất hoàn toàn trong quá trình biên dịch

  • Kết quả không quá gây ngạc nhiên. Vì bản thân trình biên dịch TypeScript được viết bằng TypeScript
    TypeScript với tư cách một ML đã được kiểm chứng hằng ngày trong các môi trường production nặng

  • Tôi từng viết trình biên dịch bằng C#, và điểm có vẻ đặc biệt ở đây chỉ là union type
    Cá nhân tôi đã chọn tránh sự dài dòng của visitor pattern, và đang chờ tính năng enum đóng để kiểm tra tính đầy đủ ở thời điểm biên dịch

    • Khi dùng một ngôn ngữ không có union type hay enum kiểu Rust, bạn sẽ rất nhớ tính năng đó
      Các phương án thay thế thường khá gượng gạo. Hoặc là có N thuộc tính nullable trong một lớp biểu diễn một sum type và dựa vào điều kiện trên tài liệu rằng “luôn chỉ có một thuộc tính non-null”, hoặc là cho nhiều lớp kế thừa từ một lớp chung; cả hai đều cảm giác nặng nề
      Nếu muốn tạo nhiều union type chồng lấn nhau, cả hai cách đều cần lặp lại hoặc phải phối hợp một cách khéo léo