知識星球
https://gilmi.me/blog/post/2016/10/14/lisp-to-js
作者 | Gil Mizrahi
譯者 | 周家未 (BriFuture) ????共計翻譯：27.0 篇 貢獻時間：864 天
我們將會在本篇文章中看到從零開始實現的編譯器，將簡單的類 LISP 計算語言編譯成 JavaScript。完整的原始碼在 這裡[1]。
我們將會：
開始吧！
1、定義語言
Lisp 族語言最迷人的地方在於，它們的語法就是樹狀表示的，這就是這門語言很容易解析的原因。我們很快就能接觸到它。但首先讓我們把自己的語言定義好。關於我們語言的語法的正規化（BNF）描述如下：
program ::= expr
expr ::= <integer> | <name> | ([<expr>])
基本上，我們可以在該語言的最頂層定義運算式並對其進行運算。運算式由一個整數（比如 5）、一個變數（比如 x）或者一個運算式串列（比如 (add x 1)）組成。
整數對應它本身的值，變數對應它在當前環境中系結的值，運算式串列對應一個函式呼叫，該串列的第一個引數是相應的函式，剩下的運算式是傳遞給這個函式的引數。
該語言中，我們保留一些內建的特殊形式，這樣我們就能做一些更有意思的事情：
let 運算式使我們可以在它的 body 環境中引入新的變數。語法如下：
let ::= (let ([<letarg>]) <body>)
letargs ::= (<name> <expr>)
body ::= <expr>
lambda 運算式：也就是匿名函式定義。語法如下：
lambda ::= (lambda ([<name>]) <body>)
還有一些內建函式： add、mul、sub、div 和 print。
讓我們看看用我們這門語言編寫的入門示例程式：
(let
((compose
(lambda (f g)
(lambda (x) (f (g x)))))
(square
(lambda (x) (mul x x)))
(add1
(lambda (x) (add x 1))))
(print ((compose square add1) 5)))
這個程式定義了 3 個函式：compose、square 和 add1。然後將計算結果的值 ((compose square add1) 5) 輸出出來。
我相信瞭解這門語言，這些資訊就足夠了。開始實現它吧。
在 Haskell 中，我們可以這樣定義語言：
type Name = String
data Expr
= ATOM Atom
| LIST [Expr]
deriving (Eq, Read, Show)
data Atom
= Int Int
| Symbol Name
deriving (Eq, Read, Show)
我們可以解析用該語言用 Expr 定義的程式。而且，這裡我們添加了新資料型別 Eq、Read和 Show 等實體用於測試和除錯。你能夠在 REPL 中使用這些資料型別，驗證它們確實有用。
我們不在語法中定義 lambda、let 或其它的內建函式，原因在於，當前情況下我們沒必要用到這些東西。這些函式僅僅是 LIST （運算式串列）的更加特殊的用例。所以我決定將它放到後面的部分。
一般來說你想要在抽象語法中定義這些特殊用例 —— 用於改進錯誤資訊、禁用靜態分析和最佳化等等，但在這裡我們不會這樣做，對我們來說這些已經足夠了。
另一件你想做的事情可能是在語法中新增一些註釋資訊。比如定位：Expr 是來自哪個檔案的，具體到這個檔案的哪一行哪一列。你可以在後面的階段中使用這一特性，打印出錯誤定位，即使它們不是處於解析階段。
Program 資料型別，可以按順序包含多個 Expr2、實現一個簡單的解析器組合庫
我們要做的第一件事情是定義一個嵌入式領域專用語言（EDSL），我們會用它來定義我們的語言解析器。這常常被稱為解析器組合庫。我們做這件事完全是出於學習的目的，Haskell 裡有很好的解析庫，在實際構建軟體或者進行實驗時，你應該使用它們。megaparsec[2] 就是這樣的一個庫。
首先我們來談談解析庫的實現的思路。本質上，我們的解析器就是一個函式，接受一些輸入，可能會讀取輸入的一些或全部內容，然後傳回解析出來的值和無法解析的輸入部分，或者在解析失敗時丟擲異常。我們把它寫出來。
newtype Parser a
= Parser (ParseString -> Either ParseError (a, ParseString))
data ParseString
= ParseString Name (Int, Int) String
data ParseError
= ParseError ParseString Error
type Error = String
這裡我們定義了三個主要的新型別。
第一個，Parser a 是之前討論的解析函式。
第二個，ParseString 是我們的輸入或攜帶的狀態。它有三個重要的部分：
Name: 這是源的名字(Int, Int): 這是源的當前位置String: 這是等待解析的字串第三個，ParseError 包含瞭解析器的當前狀態和一個錯誤資訊。
現在我們想讓這個解析器更靈活，我們將會定義一些常用型別的實體。這些實體讓我們能夠將小巧的解析器和複雜的解析器結合在一起（因此它的名字叫做 “解析器組合器”）。
第一個是 Functor 實體。我們需要 Functor 實體，因為我們要能夠對解析值應用函式從而使用不同的解析器。當我們定義自己語言的解析器時，我們將會看到關於它的示例。
instance Functor Parser where
fmap f (Parser parser) =
Parser (\str -> first f <$> parser str)
第二個是 Applicative 實體。該實體的常見用例是在多個解析器中實現一個純函式。
instance Applicative Parser where
pure x = Parser (\str -> Right (x, str))
(Parser p1) (Parser p2) =
Parser $
\str -> do
(f, rest) p1 str
(x, rest')
pure (f x, rest')
（註意：我們還會實現一個 Monad 實體，這樣我們才能使用符號）
第三個是 Alternative 實體。萬一前面的解析器解析失敗了，我們要能夠提供一個備用的解析器。
instance Alternative Parser where
empty = Parser (`throwErr` "Failed consuming input")
(Parser p1) (Parser p2) =
Parser $
\pstr -> case p1 pstr of
Right result -> Right result
Left _ -> p2 pstr
第四個是 Monad 實體。這樣我們就能連結解析器。
instance Monad Parser where
(Parser p1) >>= f =
Parser $
\str -> case p1 str of
Left err -> Left err
Right (rs, rest) ->
case f rs of
Parser parser -> parser rest
接下來，讓我們定義一種的方式，用於執行解析器和防止失敗的助手函式：
runParser :: String -> String -> Parser a -> Either ParseError (a, ParseString)
runParser name str (Parser parser) = parser $ ParseString name (0,0) str
throwErr :: ParseString -> String -> Either ParseError a
throwErr ps@(ParseString name (row,col) _) errMsg =
Left $ ParseError ps $ unlines
[ "*** " ++ name ++ ": " ++ errMsg
, "* On row " ++ show row ++ ", column " ++ show col ++ "."
]
現在我們將會開始實現組合器，這是 EDSL 的 API，也是它的核心。
首先，我們會定義 oneOf。如果輸入串列中的字元後面還有字元的話，oneOf 將會成功，否則就會失敗。
oneOf :: [Char] -> Parser Char
oneOf chars =
Parser $ \case
ps@(ParseString name (row, col) str) ->
case str of
[] -> throwErr ps "Cannot read character of empty string"
(c:cs) ->
if c `elem` chars
then Right (c, ParseString name (row, col+1) cs)
else throwErr ps $ unlines ["Unexpected character " ++ [c], "Expecting one of: " ++ show chars]
optional 將會丟擲異常，停止解析器。失敗時它僅僅會傳回 Nothing。
optional :: Parser a -> Parser (Maybe a)
optional (Parser parser) =
Parser $
\pstr -> case parser pstr of
Left _ -> Right (Nothing, pstr)
Right (x, rest) -> Right (Just x, rest)
many 將會試著重覆執行解析器，直到失敗。當它完成的時候，會傳回成功執行的解析器串列。many1 做的事情是一樣的，但解析失敗時它至少會丟擲一次異常。
many :: Parser a -> Parser [a]
many parser = go []
where go cs = (parser >>= \c -> go (c:cs)) pure (reverse cs)
many1 :: Parser a -> Parser [a]
many1 parser =
(:) <$> parser many parser
下麵的這些解析器透過我們定義的組合器來實現一些特殊的解析器：
char :: Char -> Parser Char
char c = oneOf [c]
string :: String -> Parser String
string = traverse char
space :: Parser Char
space = oneOf " \n"
spaces :: Parser String
spaces = many space
spaces1 :: Parser String
spaces1 = many1 space
withSpaces :: Parser a -> Parser a
withSpaces parser =
spaces *> parser spaces
parens :: Parser a -> Parser a
parens parser =
(withSpaces $ char '(')
*> withSpaces parser
(spaces *> char ')')
sepBy :: Parser a -> Parser b -> Parser [b]
sepBy sep parser = do
frst optional parser
rest many (sep *> parser)
pure $ maybe rest (:rest) frst
現在為該門語言定義解析器所需要的所有東西都有了。
3、為我們的語言實現解析器
我們會用自頂而下的方法定義解析器。
parseExpr :: Parser Expr
parseExpr = fmap ATOM parseAtom fmap LIST parseList
parseList :: Parser [Expr]
parseList = parens $ sepBy spaces1 parseExpr
parseAtom :: Parser Atom
parseAtom = parseSymbol parseInt
parseSymbol :: Parser Atom
parseSymbol = fmap Symbol parseName
註意到這四個函式是在我們這門語言中屬於高階描述。這解釋了為什麼 Haskell 執行解析工作這麼棒。在定義完高階部分後，我們還需要定義低階別的 parseName 和 parseInt。
我們能在這門語言中用什麼字元作為名字呢？用小寫的字母、數字和下劃線吧，而且名字的第一個字元必須是字母。
parseName :: Parser Name
parseName = do
c oneOf ['a'..'z']
cs many $ oneOf $ ['a'..'z'] ++ "0123456789" ++ "_"
pure (c:cs)
整數是一系列數字，數字前面可能有負號 -：
parseInt :: Parser Atom
parseInt = do
sign optional $ char '-'
num many1 $ oneOf "0123456789"
let result = read $ maybe num (:num) sign of
pure $ Int result
最後，我們會定義用來執行解析器的函式，傳回值可能是一個 Expr 或者是一條錯誤資訊。
runExprParser :: Name -> String -> Either String Expr
runExprParser name str =
case runParser name str (withSpaces parseExpr) of
Left (ParseError _ errMsg) -> Left errMsg
Right (result, _) -> Right result
Program 型別編寫一個解析器parseNameparseInt 可能出現上限溢位情況，找到處理它的方法，不要用 read。4、為這門語言實現一個更好看的輸出器
我們還想做一件事，將我們的程式以原始碼的形式打印出來。這對完善錯誤資訊很有用。
printExpr :: Expr -> String
printExpr = printExpr' False 0
printAtom :: Atom -> String
printAtom = \case
Symbol s -> s
Int i -> show i
printExpr' :: Bool -> Int -> Expr -> String
printExpr' doindent level = \case
ATOM a -> indent (bool 0 level doindent) (printAtom a)
LIST (e:es) ->
indent (bool 0 level doindent) $
concat
[ "("
, printExpr' False (level + 1) e
, bool "\n" "" (null es)
, intercalate "\n" $ map (printExpr' True (level + 1)) es
, ")"
]
indent :: Int -> String -> String
indent tabs e = concat (replicate tabs " ") ++ e
Program 型別編寫一個美觀的輸出器好，目前為止我們寫了近 200 行程式碼，這些程式碼一般叫做編譯器的前端。我們還要寫大概 150 行程式碼，用來執行三個額外的任務：我們需要根據需求定義一個 JS 的子集，定義一個將我們的語言轉譯成這個子集的轉譯器，最後把所有東西整合在一起。開始吧。
5、根據需求定義 JavaScript 的子集
首先，我們要定義將要使用的 JavaScript 的子集：
data JSExpr
= JSInt Int
| JSSymbol Name
| JSBinOp JSBinOp JSExpr JSExpr
| JSLambda [Name] JSExpr
| JSFunCall JSExpr [JSExpr]
| JSReturn JSExpr
deriving (Eq, Show, Read)
type JSBinOp = String
這個資料型別表示 JavaScript 運算式。我們有兩個原子型別 JSInt 和 JSSymbol，它們是由我們這個語言中的 Atom 轉譯來的，我們用 JSBinOp 來表示二元操作，比如 + 或 *，用 JSLambda 來表示匿名函式，和我們語言中的 lambda expression（lambda 運算式） 一樣，我們將會用 JSFunCall 來呼叫函式，用 let 來引入新名字，用 JSReturn 從函式中傳回值，在 JavaScript 中是需要傳回值的。
JSExpr 型別是對 JavaScript 運算式的 抽象表示。我們會把自己語言中運算式的抽象表示 Expr 轉譯成 JavaScript 運算式的抽象表示 JSExpr。但為了實現這個功能，我們需要實現 JSExpr ，並從這個抽象表示中生成 JavaScript 程式碼。我們將透過遞迴匹配 JSExpr 實現，將 JS 程式碼當作 String 來輸出。這和我們在 printExpr 中做的基本上是一樣的。我們還會追蹤元素的作用域，這樣我們才可以用合適的方式縮排生成的程式碼。
printJSOp :: JSBinOp -> String
printJSOp op = op
printJSExpr :: Bool -> Int -> JSExpr -> String
printJSExpr doindent tabs = \case
JSInt i -> show i
JSSymbol name -> name
JSLambda vars expr -> (if doindent then indent tabs else id) $ unlines
["function(" ++ intercalate ", " vars ++ ") {"
,indent (tabs+1) $ printJSExpr False (tabs+1) expr
] ++ indent tabs "}"
JSBinOp op e1 e2 -> "(" ++ printJSExpr False tabs e1 ++ " " ++ printJSOp op ++ " " ++ printJSExpr False tabs e2 ++ ")"
JSFunCall f exprs -> "(" ++ printJSExpr False tabs f ++ ")(" ++ intercalate ", " (fmap (printJSExpr False tabs) exprs) ++ ")"
JSReturn expr -> (if doindent then indent tabs else id) $ "return " ++ printJSExpr False tabs expr ++ ";"
JSProgram 型別，它可以包含多個 JSExpr ，然後建立一個叫做 printJSExprProgram 的函式來生成程式碼。JSExpr 的新型別：JSIf，併為其生成程式碼。6、實現到我們定義的 JavaScript 子集的程式碼轉譯器
我們快做完了。這一節將會建立函式，將 Expr 轉譯成 JSExpr。
基本思想很簡單，我們會將 ATOM 轉譯成 JSSymbol 或者 JSInt，然後會將 LIST 轉譯成一個函式呼叫或者轉譯的特例。
type TransError = String
translateToJS :: Expr -> Either TransError JSExpr
translateToJS = \case
ATOM (Symbol s) -> pure $ JSSymbol s
ATOM (Int i) -> pure $ JSInt i
LIST xs -> translateList xs
translateList :: [Expr] -> Either TransError JSExpr
translateList = \case
[] -> Left "translating empty list"
ATOM (Symbol s):xs
| Just f lookup s builtins ->
f xs
f:xs ->
JSFunCall <$> translateToJS f traverse translateToJS xs
builtins 是一系列要轉譯的特例，就像 lambada 和 let。每一種情況都可以獲得一系列引數，驗證它是否合乎語法規範，然後將其轉譯成等效的 JSExpr。
type Builtin = [Expr] -> Either TransError JSExpr
type Builtins = [(Name, Builtin)]
builtins :: Builtins
builtins =
[("lambda", transLambda)
,("let", transLet)
,("add", transBinOp "add" "+")
,("mul", transBinOp "mul" "*")
,("sub", transBinOp "sub" "-")
,("div", transBinOp "div" "/")
,("print", transPrint)
]
我們這種情況，會將內建的特殊形式當作特殊的、非第一類的進行對待，因此不可能將它們當作第一類函式。
我們會把 Lambda 運算式轉譯成一個匿名函式：
transLambda :: [Expr] -> Either TransError JSExpr
transLambda = \case
[LIST vars, body] -> do
vars'
JSLambda vars' <$> (JSReturn <$> translateToJS body)
vars ->
Left $ unlines
["Syntax error: unexpected arguments for lambda."
,"expecting 2 arguments, the first is the list of vars and the second is the body of the lambda."
,"In expression: " ++ show (LIST $ ATOM (Symbol "lambda") : vars)
]
fromSymbol :: Expr -> Either String Name
fromSymbol (ATOM (Symbol s)) = Right s
fromSymbol e = Left $ "cannot bind value to non symbol type: " ++ show e
我們會將 let 轉譯成帶有相關名字引數的函式定義，然後帶上引數呼叫函式，因此會在這一作用域中引入變數：
transLet :: [Expr] -> Either TransError JSExpr
transLet = \case
[LIST binds, body] -> do
(vars, vals) letParams binds
vars'
JSFunCall . JSLambda vars' <$> (JSReturn <$> translateToJS body) traverse translateToJS vals
where
letParams :: [Expr] -> Either Error ([Expr],[Expr])
letParams = \case
[] -> pure ([],[])
LIST [x,y] : rest -> ((x:) *** (y:)) <$> letParams rest
x : _ -> Left ("Unexpected argument in let list in expression:\n" ++ printExpr x)
vars ->
Left $ unlines
["Syntax error: unexpected arguments for let."
,"expecting 2 arguments, the first is the list of var/val pairs and the second is the let body."
,"In expression:\n" ++ printExpr (LIST $ ATOM (Symbol "let") : vars)
]
我們會將可以在多個引數之間執行的運運算元轉譯成一系列二元運運算元。比如：(add 1 2 3) 將會變成 1 + (2 + 3)。
transBinOp :: Name -> Name -> [Expr] -> Either TransError JSExpr
transBinOp f _ [] = Left $ "Syntax error: '" ++ f ++ "' expected at least 1 argument, got: 0"
transBinOp _ _ [x] = translateToJS x
transBinOp _ f list = foldl1 (JSBinOp f) <$> traverse translateToJS list
然後我們會將 print 轉換成對 console.log 的呼叫。
transPrint :: [Expr] -> Either TransError JSExpr
transPrint [expr] = JSFunCall (JSSymbol "console.log") . (:[]) <$> translateToJS expr
transPrint xs = Left $ "Syntax error. print expected 1 arguments, got: " ++ show (length xs)
註意，如果我們將這些程式碼當作 Expr 的特例進行解析，那我們就可能會跳過語法驗證。
Program 轉譯成 JSProgramif Expr Expr Expr 新增一個特例，並將它轉譯成你在上一次練習中實現的 JSIf 條件陳述句。7、把所有東西整合到一起
最終，我們將會把所有東西整合到一起。我們會：
ExprJSExpr我們還會啟用一些用於測試的標誌位：
--e 將進行解析並打印出運算式的抽象表示（Expr）--pp 將進行解析，美化輸出--jse 將進行解析、轉譯、並打印出生成的 JS 運算式（JSExpr）的抽象表示--ppc 將進行解析，美化輸出併進行編譯
main :: IO ()
main = getArgs >>= \case
[file] ->
printCompile =<< readFile file
["--e",file] ->
either putStrLn print . runExprParser "--e" =<< readFile file
["--pp",file] ->
either putStrLn (putStrLn . printExpr) . runExprParser "--pp" =<< readFile file
["--jse",file] ->
either print (either putStrLn print . translateToJS) . runExprParser "--jse" =<< readFile file
["--ppc",file] ->
either putStrLn (either putStrLn putStrLn) . fmap (compile . printExpr) . runExprParser "--ppc" =<< readFile file
_ ->
putStrLn $ unlines
["Usage: runghc Main.hs [ --e, --pp, --jse, --ppc ]"
,"--e print the Expr"
,"--pp pretty print Expr"
,"--jse print the JSExpr"
,"--ppc pretty print Expr and then compile"
]
printCompile :: String -> IO ()
printCompile = either putStrLn putStrLn . compile
compile :: String -> Either Error String
compile str = printJSExpr False 0 <$> (translateToJS =<< runExprParser "compile" str)
大功告成。將自己的語言編譯到 JS 子集的編譯器已經完成了。再說一次，你可以在 這裡[1] 看到完整的源檔案。
用我們的編譯器執行第一節的示例，產生的 JavaScript 程式碼如下：
$ runhaskell Lisp.hs example.lsp
(function(compose, square, add1) {
return (console.log)(((compose)(square, add1))(5));
})(function(f, g) {
return function(x) {
return (f)((g)(x));
};
}, function(x) {
return (x * x);
}, function(x) {
return (x + 1);
})
如果你在自己電腦上安裝了 node.js，你可以用以下命令執行這段程式碼：
$ runhaskell Lisp.hs example.lsp | node -p
36
undefined
via: https://gilmi.me/blog/post/2016/10/14/lisp-to-js
作者：Gil Mizrahi[4] 選題：oska874 譯者：BriFuture 校對：wxy
本文由 LCTT 原創編譯，Linux中國 榮譽推出