文最初发布于 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公司久呆的人，到底有多会划水？