文最初發布于 Matt Might 的個人博客。

本文介紹了多種解釋器實現。通過修改最后一個解釋器，你應該可以快速測試關于編程語言的新想法。如果你希望有一種語法不一樣的語言，就可以構建一個解析器，把 s-表達式轉儲。這樣，你就可以干凈利落地將語法設計與語義設計分開。

實現一門編程語言是任何程序員都不應該錯過的經驗；這個過程可以培養你對計算的深刻理解，而且很有趣。

本文直擊本質，把整個過程歸結為：一個面向函數式（但圖靈等價）編程語言的 7 行解釋器，而其實現只需要大約 3 分鐘。

這個 7 行的解釋器展示了許多解釋器中都存在的可擴展架構——《計算機程序的結構與解釋》中的 eval/apply 設計模式：

本文中總共有三種語言的實現：

• 一個使用 Scheme 耗時 3 分鐘實現的 7 行解釋器；
• 使用Racket重新實現；
• 一個耗時“一下午”實現的 100 行解釋器，實現了頂層綁定形式、顯式遞歸、副作用、高階函數等功能。如果想要實現一門功能更豐富的語言，那么最后一個解釋器是一個不錯的起點。

一門小語言（但圖靈等價）

最容易實現的編程語言是一種極簡的高階函數式編程語言，名為λ演算（lambda calculus）。

實際上，λ演算是所有主要的函數式語言的核心——Haskell、Scheme 和 ML——但它也存在于 JavaScript、Python 和 Ruby 中。它甚至隱藏在 Java 中，不知道你是否知道在哪里可以找到它。

λ演算簡史

阿隆佐·丘奇在 1929 年開發了λ演算。

那時，它還不叫編程語言，因為當時沒有計算機；沒有什么東西可以“編程”。

它實際上只是一個用于函數推理的數學符號。幸運的是，阿隆佐·丘奇有一個博士生叫艾倫·圖靈。

艾倫·圖靈定義了圖靈機，這成為通用計算機第一個公認的定義。

人們很快發現，λ演算和圖靈機是等價的：任何能用λ演算描述的函數都能在圖靈機上實現，而任何能在圖靈機上實現的函數都能用λ演算描述。

值得注意的是，λ演算中只有三種表達式：變量引用、匿名函數和函數調用。

匿名函數

匿名函數的編寫采用“lambda-dot”標記法，如下所示：

 (λ v . e)

復制代碼

該函數接受參數v ，返回值e 。如果用 JavaScript 編寫，上述代碼等價于：

 function (v) { return e ; } 

復制代碼

函數調用

函數調用的寫法是使兩個表達式相鄰：

 (f e)

復制代碼

JavaScript（或其他任何語言）的寫法如下：

 f(e)

復制代碼

示例

將參數原樣返回的恒等函數寫法如下：

 (λ x . x)

復制代碼

我們可以將恒等函數應用于恒等函數：

 ((λ x . x) (λ a . a))

復制代碼

（返回當然也是恒等函數。）下面這個程序更有意思一些：

 (((λ f . (λ x . (f x))) (λ a . a)) (λ b . b))

復制代碼

你能搞懂它做了什么嗎？

這到底是怎樣的一種“編程”語言？

乍一看，這門簡單的語言似乎缺少遞歸和迭代，更不用說數值、布爾、條件、數據結構等其他東西。這種語言怎么可能是通用的呢？

λ演算達到圖靈等價是通過兩個最酷的編程黑科技實現的：Church 編碼和 Y 組合子。

關于 Y 組合子，我已經寫過一篇文章，關于Church編碼，也寫過一篇。不過，你不想讀這些文章也沒事，我只需一個程序就可以說服你，λ演算的功能遠超你的預期：

 ((λ f . (f f)) (λ f . (f f)))

復制代碼

這個看上去無害的程序名為 Omega，如果你試圖執行它，就發現它不會終止！（看看你能不能找出原因）。

實現λ演算

下面是用 R5RS Scheme 耗時 3 分鐘實現的一個 7 行λ演算解釋器。從技術上講（下文有解釋），它是一個基于環境的指示型解釋器。

; eval將一個表達式和一個環境轉換成一個值
(define (eval e env) (cond
  ((symbol? e)       (cadr (assq e env)))
  ((eq? (car e) 'λ)  (cons e env))
  (else              (apply (eval (car e) env) (eval (cadr e) env)))))


; apply將一個函數和一個參數轉換成一個值
(define (apply f x)
  (eval (cddr (car f)) (cons (list (cadr (car f)) x) (cdr f))))


; 從stdin讀取并解析，然后求值：
(display (eval (read) '())) (newline)

復制代碼

這段代碼將從 stdin 讀取一個程序，解析它，求值并打印結果。(去掉注釋和空行，它只有 7 行）。Scheme 的read函數簡化了詞法分析和解析——只要你愿意生活在“平衡圓括號”（即s-表達式）的語法世界中。(如果不愿意，你就必須仔細研究解析中的詞法分析；可以從我的一篇關于詞法分析的文章入手）。在 Scheme 中，read從 stdin 中獲取括號括起來的輸入，并將其解析為一棵樹。

eval 和apply 兩個函數構成了解釋器的核心。盡管是在 Scheme 中，但我們可以給予這些函數概念上的“簽名”：

 eval  : Expression * Environment -> Value
 apply : Value * Value -> Value


 Environment = Variable -> Value
 Value       = Closure
 Closure     = Lambda * Environment

復制代碼

eval函數接收一個表達式和一個環境然后轉換為一個值。表達式可以是一個變量，一個 lambda 項或一個應用程序。環境是一個從變量到值的映射，用來定義一個開項的自由變量。（開項是一個變量的非綁定出現。）例如，考慮一下表達式（λ x . z）。這個項是開放的，因為我們不知道z是什么。

由于用的是 R5RS Scheme，我們可以使用關聯列表來定義環境。

閉包是一個函數的編碼，它將一個（可能是開放的）lambda 表達式與一個環境配對，以定義其自由變量。換句話說，一個閉包封閉了一個開項。

使用 Racket 的實現更簡潔

Racket是 Scheme 的一種方言，它功能齊備，可以把事情做好。Racket 提供了一個可以清理解釋器的匹配結構，如下所示：

#racket語言


; 引入匹配庫：
(require racket/match)


; eval匹配表達式類型：
(define (eval exp env) (match exp
  [`(,f ,e)        (apply (eval f env) (eval e env))]
  [`(λ ,v . ,e)   `(closure ,exp ,env)]
  [(? symbol?)     (cadr (assq exp env))]))


; apply用一個匹配來析構函數：
(define (apply f x) (match f
  [`(closure (λ ,v . ,body) ,env)
    (eval body (cons `(,v ,x) env))]))


; 讀入、解析、求值：
(display (eval (read) '()))    (newline)

復制代碼

這個代碼多點，但更簡潔，更容易理解。

一門更大的語言

λ演算是一門很小的語言。即便如此，其解釋器的 eval/apply 設計也可以擴展到更大的語言。例如，用大約 100 行代碼，我們可以為一個相當大的 Scheme 子集實現一個解釋器。

考慮一種具有各種表達形式的語言：

1. 變量引用，如：x、foo、save-file。
2. 數值和布爾常量，如：300、3.14、#f。
3. 基本操作，如：+、-、<=。
4. 條件：(if condition if-true if-false)。
5. 變量綁定：(let ((var value) ...) body-expr)。
6. 遞歸綁定：(letrec ((var value) ...) body-expr)。
7. 變量可變：(set! var value)。
8. 定序：(begin do-this then-this)。現在，為這門語言添加 3 個頂層形式：
9. 函數定義：(define (proc-name var ...) expr)。
10. 全局定義：(define var expr)。
11. 頂層表達式：expr。下面是完整的解釋器，其中包括測試工具和測試用例：

#語言racket


(require racket/match)


;; 計算在eval和apply之間切換。


; eval分派表達式類型：
(define (eval exp env)
  (match exp
    [(? symbol?)          (env-lookup env exp)]
    [(? number?)          exp]
    [(? boolean?)         exp]
    [`(if ,ec ,et ,ef)    (if (eval ec env)
                              (eval et env)
                              (eval ef env))]
    [`(letrec ,binds ,eb) (eval-letrec binds eb env)]
    [`(let    ,binds ,eb) (eval-let binds eb env)]
    [`(lambda ,vs ,e)    `(closure ,exp ,env)]
    [`(set! ,v ,e)        (env-set! env v e)]
    [`(begin ,e1 ,e2)     (begin (eval e1 env)
                                 (eval e2 env))]
    [`(,f . ,args)        (apply-proc
                           (eval f env) 
                           (map (eval-with env) args))]))


; 一個方便的Currying eval的封裝器：
(define (eval-with env) 
  (lambda (exp) (eval exp env)))


; eval for letrec:
(define (eval-letrec bindings body env)
  (let* ((vars (map car bindings))
         (exps (map cadr bindings))
         (fs   (map (lambda _ #f) bindings))
         (env* (env-extend* env vars fs))
         (vals (map (eval-with env*) exps)))
    (env-set!* env* vars vals)
    (eval body env*)))


; eval for let:
(define (eval-let bindings body env)
  (let* ((vars (map car bindings))
         (exps (map cadr bindings))
         (vals (map (eval-with env) exps))
         (env* (env-extend* env vars vals)))
    (eval body env*)))
    
; 將一個過程作用于參數：
(define (apply-proc f values) 
  (match f
    [`(closure (lambda ,vs ,body) ,env) 
     ; =>
     (eval body (env-extend* env vs values))]
    
    [`(primitive ,p)
     ; =>
     (apply p values)]))


;; 環境將變量映射到包含值的可變單元格。


(define-struct cell ([value #:mutable]))


; 清空環境：
(define (env-empty)  (hash))


; 初始化環境，綁定基本操作：
(define (env-initial)
  (env-extend* 
   (env-empty)
   '(+  -  /  *  <=  void  display  newline)
   (map (lambda (s) (list 'primitive s))
   `(,+ ,- ,/ ,* ,<= ,void ,display ,newline))))


; 查找一個值：
(define (env-lookup env var)
  (cell-value (hash-ref env var)))


; 在環境中設置一個值：
(define (env-set! env var value)
  (set-cell-value! (hash-ref env var) value))


; 通過多個綁定擴展環境：
(define (env-extend* env vars values)
  (match `(,vars ,values)
    [`((,v . ,vars) (,val . ,values))
     ; =>
     (env-extend* (hash-set env v (make-cell val)) vars values)]
    
    [`(() ())
     ; =>
     env]))


; 通過多次賦值改變環境：
(define (env-set!* env vars values)
  (match `(,vars ,values)
    [`((,v . ,vars) (,val . ,values))
     ; =>
     (begin
       (env-set! env v val)
       (env-set!* env vars values))]
    
    [`(() ())
     ; =>
     (void)]))


;; 計算測試。


; 定義新的語法，使測試看起來更漂亮：
(define-syntax 
  test-eval 
  (syntax-rules (====)
    [(_ program ==== value)
     (let ((result (eval (quote program) (env-initial))))
       (when (not (equal? program value))
         (error "test failed!")))]))


(test-eval
  ((lambda (x) (+ 3 4)) 20)
  ====
  7)


(test-eval
  (letrec ((f (lambda (n) 
                 (if (<= n 1)
                     1
                     (* n (f (- n 1)))))))
    (f 5))
  ====
  120)


(test-eval
  (let ((x 100))
    (begin
      (set! x 20)
      x))
  ====
  20)


(test-eval
  (let ((x 1000))
    (begin (let ((x 10))
             20)
           x))
  ====
  1000)


;; 程序被翻譯成一個letrec表達式。


(define (define->binding define)
  (match define
    [`(define (,f . ,formals) ,body)
     ; =>
     `(,f (lambda ,formals ,body))]
    
    [`(define ,v ,value)
     ; =>
     `(,v ,value)]
    
    [else 
     ; =>
     `(,(gensym) ,define)]))


(define (transform-top-level defines)
  `(letrec ,(map define->binding defines)
     (void)))


(define (eval-program program)
  (eval (transform-top-level program) (env-initial)))


(define (read-all)
  (let ((next (read)))
    (if (eof-object? next)
        '()
        (cons next (read-all)))))


; 讀入一個程序并計算：
(eval-program (read-all))

復制代碼

下載源代碼，請點擊https://matt.might.net/articles/implementing-a-programming-language/minilang.rkt?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NTU0NTMzMzAsImZpbGVHVUlEIjoibG9xZVcyRXl2d0hkSkxBbiIsImlhdCI6MTY1NTQ1MzAzMCwidXNlcklkIjoyMDQxOTA5MH0.Nv5UyUdCUJNT7c0kIaPSE0g0f4k9Ed26rLl2Bu5RpG4

結語

通過修改最后一個解釋器，你應該可以快速測試關于編程語言的新想法。

如果你希望有一種語法不一樣的語言，就可以構建一個解析器，把 s-表達式轉儲。這樣，你就可以干凈利落地將語法設計與語義設計分開。

查看英文原文：

https://matt.might.net/articles/implementing-a-programming-language?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NTU0NTMzMzAsImZpbGVHVUlEIjoibG9xZVcyRXl2d0hkSkxBbiIsImlhdCI6MTY1NTQ1MzAzMCwidXNlcklkIjoyMDQxOTA5MH0.Nv5UyUdCUJNT7c0kIaPSE0g0f4k9Ed26rLl2Bu5RpG4

avaScript是一種發展迅速的語言。這篇文章，我想展示一些有關如何在JavaScript中應用函數式編程的示例。

JavaScript中的函數式編程

即使函數式編程可以極大地改善應用程序的代碼，但其原理在開始時可能會有些挑戰。由于詳細解釋所有這些都將花費大量時間，因此我們決定使用兩個實際的代碼示例來介紹這些概念

1.Maybe Monad

在第一個示例中，我們找到一種避免驗證變量是否為Null的方法。假設在我們的應用程序中，我們可以找到具有以下格式的用戶：

const someUser = {
 name: 'some_name',
 email: 'some@email.com',
 settings: {
  language: 'sp'
 }
};

有一個功能，可以以用戶設置的語言返回歡迎消息。

const allGreetings = {
 'en': '嗨',
 'sp': '你好',
 'fr': '歡迎你'
};
const getGreetingForUser = (user) => {
 //將要執行
}

來看一個遵循命令式模型的“ getGreetingForUser”函??數的實現：

const getGreetingForUser = (user) => {
 if (!user) {
   return allGreetings.en;
 }
 if (user.settings && user.settings.language) {
   if (allGreetings[user.settings.language]) {
     return allGreetings[user.settings.language]
   } else {
     return allGreetings.en;
   }
 } else {
   return allGreetings.en;
 }
};
console.log(getGreetingForUser(someUser));

如上面所看到的，必須檢查用戶是否已經存在，是否已設置語言，以及是否已準備好歡迎消息。如果出現問題，我們將以默認語言返回一條消息。

現在，讓我們看一下相同的函數，但是這次我們將在其實現中使用函數式編程：

const getGreetingForUser = (user) => {
  return RamdaFantasy.Maybe(user)
    .map(Ramda.path(['settings', 'language']))
    .chain(maybeGreeting);
};
const maybeGreeting = Ramda.curry((greetingsList, userLanguage) => {
  return RamdaFantasy.Maybe(greetingsList[userLanguage]);
})(allGreetings);
console.log(getGreetingForUser(someUser).getOrElse(allGreetings.en));

為了處理可能為null或未定義的情況，我們將使用Maybe Monad。這使我們可以在對象周圍創建包裝器，并為空對象分配默認行為。

讓我們比較兩種解決方案：

//代替驗證用戶是否為空
if (!user) {
  return allGreetings.en;
}
//我們將用：
RamdaFantasy.Maybe(user) //我們將用戶添加到包裝器中

//代替：
 if (user.settings && user.settings.language) {
   if (allGreetings[user.settings.language]) {
//我們將用：
 <userMaybe>.map(Ramda.path(['settings', 'language'])) //如果存在數據，映射將會用它

//不是在else中返回默認值：
 return indexURLs['en'];
.getOrElse（allGreetings。EN）
// 指定的默認值。

2 Either Monad

當我們知道存在空錯誤時的默認行為時，Maybe Monad非常有用。

但是，如果我們有一個引發錯誤的函數，或者我們將各種引發錯誤的函數鏈接在一起，并且我們想知道哪個發生了故障，則可以改用Either Monad。

現在，讓我們假設我們要計算產品的價格，同時考慮增值稅和可能的折扣。我們已經有了以下代碼：

const withTaxes = (tax, price) => {
2
 if (!_.isNumber(price)) {
3
 return new Error("Price is not numeric");
4
 }
5
 return price + (tax * price);
6
};
7
const withDiscount = (dis, price) => { 
8
  if (!_.isNumber(price)) { 
9
    return new Error("Price is not numeric"); 
10
  } 
11
  if (price < 5) 
12
    return new Error("Discounts not available for low-priced items"); 
13
  } 
14
  return price - (price * dis);5
}; 
const isError = (e) => e && e.name === 'Error';
const calculatePrice(price, tax, discount) => { 
//將要執行
}

讓我們來看一個遵循命令式模型的“ calculatePrice”函數的實現：

const calculatePrice = (price, tax, discount) => {
  const priceWithTaxes = withTaxes(tax, price);
  if (isError(priceWithTaxes)) {
    return console.log('Error: ' + priceWithTaxes.message);
  }
  const priceWithTaxesAndDiscount = withDiscount(discount, priceWithTaxes);
  if (isError(priceWithTaxesAndDiscount)) {
    return console.log('Error: ' + priceWithTaxesAndDiscount.message);
  }
  console.log('Total Price: ' + priceWithTaxesAndDiscount);
}
//我們計算出價值25的產品（含21％的增值稅和10％的折扣）的最終價格。
 calculatePrice(25, 0.21, 0.10)

現在，讓我們了解如何使用Either Monad重寫此函數。

都有兩個構造函數，Left和Right。我們要實現的是將異常存儲到Left構造函數，并將正常結果（快樂路徑）存儲到Right構造函數。

首先，將更改已經存在的withTaxes和withDiscount函數，以便在出現錯誤時它們返回Left，在一切正常的情況下返回Right：

const withTaxes = Ramda.curry((tax, price) => {
  if (!_.isNumber(price)) {
    return RamdaFantasy.Either.Left(new Error("Price is not numeric"));
  }
  return RamdaFantasy.Either.Right(price + (tax * price)); 
});
const withDiscount = Ramda.curry((dis, price) => {
  if (!_.isNumber(price)) {
    return RamdaFantasy.Either.Left(new Error("Price is not numeric")); 
  }
  if (price < 5) { 
    return RamdaFantasy.Either.Left(new Error("Discounts not available for low-priced items")); 
  } 
  return RamdaFantasy.Either.Right(price - (price * dis)); 
});

然后，我們為Right案例創建一個函數（顯示價格），為Left案例創建另一個函數（顯示錯誤），然后使用它們創建Either Monad：

const showPrice = (total) => { console.log('Price: ' + total) }; 
const showError = (error) => { console.log('Error: ' + error.message); }; 
const eitherErrorOrPrice = RamdaFantasy.Either.either(showError, showPrice);

最后，只需要執行Monad來計算最終價格：

//計算出價值25的產品（含21％的增值稅和10％的折扣）的最終價格。
 eitherErrorOrPrice(
   RamdaFantasy.Either.Right(25)
     .chain(withTaxes(0.21))
     .chain(withDiscount(0.1))
)

結論：JavaScript中的函數式編程

正如我們所看到的，一旦用Maybe和Either單子分解了代碼，就沒有那么復雜了。如果使用得當，它們可以使我們的代碼更易于閱讀和維護。

唯一的不便是我們需要克服的初始障礙，但這可以通過在網上一些示例并進行一些測試來完成。

喜歡可以關注一下哦。

半夜的一次斜眸，我發現了支付寶灰色產業的一角

得知開源會削弱對中國的技術封鎖，特朗普氣炸了

用漫畫讓你清楚了解linux內核，看懂了么？

你用大量 if else，而不用switch的原因，if真香啊

能在996公司久呆的人，到底有多會劃水？