Skip to content

Instantly share code, notes, and snippets.

@CindyLinz

CindyLinz/BYOHC工作坊proposal.md Secret

Last active July 29, 2020 01:59
Show Gist options
  • Save CindyLinz/975dce9755ebeec6e4a5 to your computer and use it in GitHub Desktop.
Save CindyLinz/975dce9755ebeec6e4a5 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
BYOHC工作坊proposal.md

自造不需要 Haskell 環境的 Haskell 編譯器工作坊

BYOHC - Build Your Own Haskell Compiler Workshop

預期成果

  • 主要成果

    • 完成一個可以在自己指定的環境裡使用的 Haskell 直譯器或編譯器. 效能不一定很好, 應該還會有改進空間, 但是可以用, 至少可以滿足自己想要應用的情境. 而且因為是自己親手打造的, 自己完全了解它, 隨時覺得不滿意就可以動手改它.

  • 次要成果

    • 對 Haskell 在語法與運作機制方面會相當理解.

    • 獲得 Functional Language 視角, 用這個視角構造程式, 即使在別的語言裡也可以寫出容易講出正確性的程式.

條件需求

  • 不需要先會 Haskell (除非你希望執行的平台就是 Haskell....)

    但是隨著活動進行，需要把一部分的用法補起來，由於開發目的相似， 可以參考別人的寫法，所以上手速度應該會比較快

    不過就算不會, 後來應該也學會了 (運作機制的那一面)

  • 會一個程式語言

    依你希望做出來的 compiler 與 compile 出來的程式是在哪裡跑, 你需要會這個平台可以用的語言. 就是...

    • 如果想要在 JVM 平台跑, 需要會 Java 或 Clojure 或 Scala.. 欸, 如果會 bytecode 可能更好;
    • 如果想在 .Net/mono 環境跑, 需要會 C# 或其他可以在 .Net/mono 執行的語言;
    • 如果想要在 iOS 平台跑, 需要會 ObjectC 或 swift;
    • 如果想要在瀏覽器裡面跑, 需要會 Javascript 或相關的 Coffeescript, Livescript, TypeScript 等等;
    • 如果想在有 Lua 的環境就能跑, 那要會 Lua;
    • 如果想在別的 script language 環境跑, 例如 Perl, Python, Ruby, PHP.. 那就要會相對應的語言;
    • 如果想要作成 native, 那需要會 C 或 C++ 或 Rust 或 Haskell..

時間

九月24日(四)開始, 每月第二與最後一個星期四 (就是把第一個星期四的 Functional Thursday 夾在中間)

晚上 19:30 ~ 21:30

地點

福州街11號 滴咖啡 二樓房間 (要脫鞋)

福州街11號 滴咖啡 照片

費用

沒有

進行方式

有些是在聚會之外的時間自主進行的. 每次結束前, 會指定下一次聚會以前要實作的作品, 或是需要閱讀的材料, 也可能兩者皆有. 根據大家的進展還有平常忙碌的程度我們可以一邊進行一邊調整進度快慢. 希望不要快到忙不過來, 也不要慢到無趣這樣 ^^

每次聚會前半場展示兩週以來的成果, 執行實作的程式, 說明程式碼的架構; 如果這次是閱讀的話, 就嘗試解說讀到的內容, 如果有疑問就提問與解答.

後半會決定下一次的進度, 檢討調整接下來的路線圖看需不需要修改, 或是有時候我會準備一些會用到的東西.

如果要實作的目標有好幾種可以選擇的作法, 那麼會先請每人預告一下自己想採用的作法 (如果後來發現用起來不順想換方法也是可以的)

如果要閱讀的東西是理論型的, 那每一個人都讀; 而如果要閱讀的東西是別人的參考實作, 那會分配著讀 (同樣目的的不同作法), 下一次來再互相教這樣.

線上討論平台

不完整的有一句沒一句的閒聊用 gitter.im #CindyLinz/BuildYourOwnHaskellCompiler

較完整的像一篇文章性質的在 Functional Thursday FB 社團 發文討論.

如果實作中遇到聚會時沒想到的問題, 或是臨時想到什麼都可以講.

預期路線圖

安排這步驟時, 是盡可能每一個新進展都可以有可以跑跑看會動的東西, 比較有感覺有興趣; 而不是以工作量盡量少來考量.

由於本活動以做出能用的作品為目標, 所以這邊提出來的演算法名字, 在實作時不著重於原汁原味地重現, 汲取它的精神, 可能會作些變型, 達到自己想要使用的目的為主. 有些東西是同樣概念的不同形式, 所以也有可能選了要實作某 A 演算法, 然後實作中為了方便作些微調, 最後它和演算法 B 根本一模一樣 XD 但... 無所謂 ^^

  1. 將 Lambda Calculus 帶進你的世界 -- 實作 interpreter

    1. 實作 untyped Lambda Calculus interpreter (簡稱 ULCi 好了)

      • 介紹 untyped Lambda Calculus, normal form
      • 要採取 normal order evaluation strategy, 嗯, 到時會解釋這是什麼意思 (或是自己先查 wikipedia 也行)
      • 介紹 S-expression, 與一個我暫時想了的省事的程式內 language 表示方式
      • 會示範用 Lambda Calculus 可以處理多少運算 (this is amazing)

    2. 將 ULCi 加上內建資料型態與對其操作的函數, 調整 evaluation strategy 為 call-by-name 或 call-by-need

      • 不作 type check, 假設輸入的程式碼都是正確的
      • 內建資料型態是不以 lambda 表示的資料
      • 介紹 head normal form

    3. 加上外部介面 (FFI)

      • 介紹純函數對副作用的乾溼分離處理機制 (就是 Haskell 的 IO Monad)

      • 有了 FFI, 就可以讓我們的 ULCi 可以利用執行環境所提供的功能了

        • 例如說如果是實作於 JVM 環境, 那就可以隨意使用任意的 Java 函式庫
        • 如果是實作於瀏覽器環境, 那就可以拿來操作網頁裡的元件, 處理事件等等

  2. 將 Haskell 化為 Untyped Lambda Calculus

    1. 使用 Haskell 的 haskell-src-ext package 來 parse Haskell

      • 把 haskell-src-ext 處理 Haskell 程式碼產生出來的 Haskell 資料結構印成我們可以接受的格式

      • 我們先確認這個流程可行, 所以只先限制處理簡單的程式碼, 目標是讓

        main = putStrLn "Hello World"

        可以執行就行了. (其變化型就自己想做才做)

    2. 支援 desugar, type inference 之後的程式碼

      • 每一個 expr 或 binding 都加 type signature
      • 用 GADT 定義 data
      • 支援 let..in 語法 (為了遞迴 binding 一定要有這個, 不過 = 左邊一定是變數, 不處理 pattern)
      • 用 case..of destruct data component (沒有 guard, 沒有 view pattern, 而且限制只有一層 algebraic data constructor)
      • 函數定義都沒有參數 (body 放 lambda)
      • 支援 existential type, higher order function
      • 不支援 operator data constructor
      • 不處理 type inference / type check
      • 不支援 operator
      • 沒有 type class

    3. 作出上列基本語法範圍內的 type inference / type check (之一)

      • 可用 Haskell 實作 (那就是 type 補完以後再生出 ULC 程式), 也可以用自選的語言實作 (那就是在 ULC 端自己加上 type 表示方式之後再處理)
      • 先只實作 Hindley-Milner type system, Algorithm W 可以處理的範圍

    4. type inference / type check (之二)

      • 實作 bi-directional type inference 以支援 rank N type / existential type

    5. 支援 type class / instance

      • 以 desugar 的方式實作

    6. 將 type inference / type check 擴充至 type class / instance

      • 實作 functional dependency 與 data family

    7. 實作 desugar

      • 如果 type 處理是 Haskell 實作, 這裡一定要用 Haskell 實作; 不然可以選用 Haskell 或自選的語言實作
      • 必要的
        • 支援 ADT 定義 data 語法
        • 支援 Record Syntax
        • 支援 type 語法, type family
        • 支援 where 語法
        • 支援 if..then..else 語法
        • function 定義可以有參數列, 參數的位置可以寫 pattern
        • let..in 與 where 裡面可以有 pattern
        • pattern 可以巢狀很多層
        • pattern 可以有 guard
        • 支援 do-notation
        • 支援 operator
        • 支援 infix function
        • 支援 section
        • 支援 fixity
        • 支援基本 list 語法
        • 支援 string 語法
        • 支援不同進制的整數 literal
      • 次要的
        • 支援 Record pun, Record wildcards
        • 支援 view pattern
        • 支援 pattern guard
        • 支援 multi-way-if 語法
        • 支援 lambda case 語法
        • 支援 tuple section
        • 支援 mdo 與 rec
        • ...
      • 好多啊... 想到想用再自己列好嗎 /_\
      • 也許我們該分頭準備一些測試用 input 程式碼, 以程式碼來指定所用到的 feature
      • 又也許這一段我們該分頭協作, 把轉換 rule 貼到共用空間 -- 如果大家都是用 Haskell 寫這部分的話.

    8. 實作 import / export

      • 還有 mutual recursive import

    9. 實作 preprocessor (?)

    10. 實作 Template Haskell (?)

    11. 將用到的 haskell-src-ext, 自己實作的 desugar, type inferenece/check 都轉換成 ULC

      • 這一步要成功做到, 才能作出能完全只在自己選的環境裡執行的 Haskell compiler / interpreter
      • 不過這一區塊 (Haskell to ULC) 只要任何人是完全用 Haskell 實作的, 而且做成功了, 大家都可以去接來用在自己的環境裡..

  3. 讓 Lambda Calculus 在你的世界裡飛 -- 實作 compiler

    1. 閱讀參考別人的 runtime 實作

      • 比較在意原創思考, 或是要享受創作過程的人可以跳過這段

      • 看一下不同實作的特點, 再考慮自選的環境特性要怎樣比較適合

      • 目前我有找到值得讀的有: (陸續再加, 也請各位幫忙提供)

        • GHC 用的 STG (Spineless Tagless G-Machine)

    2. 閱讀參考別人的記憶體管理與 garbage collector (GC)

      • 比較在意原創思考, 或是要享受創作過程的人可以跳過這段

      • 如果使用的平台環境有提供記憶體管理與 GC 機制的話 (例如說 JVM, script, 或非 asm.js 的 javascript), 也可以跳過這段

      • 目前找到值得讀的有: (陸續再加, 也請各位幫忙提供; 這個應該會比前一項 runtime 多很多, 要選一選)

    3. 設計自己的資料結構與規劃採用的記憶體管理機制

    4. 實作記憶體管理

    5. 實作程式碼生成, 以及程式啟動執行流程

    6. 實作外部介面 (FFI)

  4. 讓 Lambda Calculus 在你的世界裡生根 -- 實作 platform driver (好多好多 library)

    • 選擇性地 porting 支援 Haskell Standard Library, 以自己用得到的為主, 而且有些 library 可能天生就不適合在選擇的平台上用. 有些是用純 Haskell 實作的 library, 如果剛好要用到, 希望最好是讓我們自己實作的 compiler / interpreter 可以直接使用它.

    • 這部分大家的目的環境差異較大, 不會有大家一起的規劃進度

    • 而且我想大家應該不會都拖到最後階段才做, 在 ULC interpreter 完成的時候應該就會開始陸續做來用了

@shhyou
Copy link

shhyou commented Aug 20, 2015

期待！可惜無法實體的出席了QQ

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment