實(shí)現(xiàn)一門編程語言對(duì)任何程序員來說都是值得擁有的經(jīng)驗(yàn)，因?yàn)樗芗由钅銓?duì)計(jì)算原理的理解，并且還很有趣。

在這篇文章中，我已經(jīng)讓整個(gè)過程回歸到它的本質(zhì)：為一種函數(shù)式（圖靈等價(jià)）編程語言設(shè)計(jì)7行代碼的解釋器。大概只需要3分鐘就能實(shí)現(xiàn)

這個(gè)7行代碼的解釋器展示了在眾多解釋器中同時(shí)存在的一個(gè)可升級(jí)的體系結(jié)構(gòu)–eval/apply設(shè)計(jì)模式。Structure and Interpretation of Computer Programs這本書提到過該模式。

在這篇文章中總計(jì)有三門語言的實(shí)現(xiàn)：

一個(gè)是scheme語言的7行，3分鐘實(shí)現(xiàn)的解釋器

一個(gè)是Racket語言的重實(shí)現(xiàn)

最后一個(gè)是100行、“1-afternoon”解釋器，它實(shí)現(xiàn)了高級(jí)綁定形式、顯示遞歸、額外作用、高階函數(shù)式等等

對(duì)于掌握一門更豐富的語言來說，最后一個(gè)解釋器是一個(gè)好起點(diǎn)

一個(gè)小型(圖靈機(jī)等價(jià))語言

最容易實(shí)現(xiàn)的一門編程語言是一個(gè)叫做λ運(yùn)算的極簡(jiǎn)單、高階函數(shù)式編程語言

λ運(yùn)算實(shí)際上存在于所有主要的功能性語言的內(nèi)核中：Haskell, Scheme、 ML，但是它也存在于JavaScript、Python、Ruby中。它甚至隱藏在Java中，如果你知道到哪里去找它。

歷史簡(jiǎn)介

1929年Alonzo Church開發(fā)出λ演算

在那時(shí)，lambda calculus不被叫做編程語言因?yàn)闆]有計(jì)算機(jī)，所以沒有編程的概念。

它僅僅是一個(gè)推演函數(shù)的數(shù)學(xué)標(biāo)記。

幸運(yùn)的是，Alonzo Church有一個(gè)叫作艾倫·圖靈的哲學(xué)博士。

艾倫·圖靈定義了圖靈機(jī)，圖靈機(jī)成了第一個(gè)被接受的通用計(jì)算機(jī)定義

不久后發(fā)現(xiàn)lambda calculus和圖靈機(jī)是等價(jià)的：任何用λ演算描述的功能可以在圖靈機(jī)上實(shí)現(xiàn)；并且在圖靈機(jī)上實(shí)現(xiàn)的任何功能可以用λ演算描述

值得注意的是在lambda calculus中僅有三種表達(dá)式：變量引用，匿名函數(shù)、函數(shù)調(diào)用

匿名函數(shù)：

(λv.e)

匿名函數(shù)以”λ-.”標(biāo)記開始，所以 (λ v . e)函數(shù)用來接收一個(gè)參數(shù)v并返回值e。

如果你用JavaScript編程，格式function (v) { return e ; }是相同的。

函數(shù)調(diào)用：

(fe)

函數(shù)調(diào)用用兩個(gè)臨近的表達(dá)式表示：(f e)

f(e)

在JavaScript中（或者其他任何語言），寫為f(e)

Examples

(λ x . x)

例如：

恒等函數(shù)（identity function），僅僅返回它的參數(shù)值，簡(jiǎn)單地寫為(λ x . x)

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

我們可以將這個(gè)恒等函數(shù)應(yīng)用到一個(gè)恒等函數(shù)上：

((λ x . x) (λ a . a))（僅返回這個(gè)恒等函數(shù)本身）

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

這兒有一個(gè)更有趣的程序：

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

你能弄清楚它是干嘛的？

等一下！見鬼，這怎么算一門編程語言？

乍一看，這門簡(jiǎn)單語言好像缺乏遞歸和迭代，更不用說數(shù)字、布爾值、條件語句、數(shù)據(jù)結(jié)構(gòu)和剩余其他的。這樣的語言怎么可能成為通用的呢？

λ演算實(shí)現(xiàn)圖靈機(jī)-等價(jià)的方式是通過兩種最酷的方式：

邱奇編碼（Church encoding）和Y combinator（美國著名企業(yè)孵化器）

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

我已經(jīng)寫了兩篇關(guān)于Y combinator和邱奇編碼的文章。

但是，你如果不想讀它們的話，我可以明確的告訴你比起你期望的僅一個(gè)((λ f . (f f)) (λ f . (f f)))程序來說 有更多的 lambda calculus知識(shí)。

表面上開始的程序叫做Ω，如果你嘗試運(yùn)行它的話，它不會(huì)終止（想一下你是否明白其中原因）

實(shí)現(xiàn)λ演算

下面是基于Scheme語言標(biāo)準(zhǔn)(R5RS)的7行、3分鐘λ演算解釋器。在術(shù)語中，它是一個(gè)依賴環(huán)境的指示解釋器

; eval takes an expression and an environment to a value

(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 takes a function and an argument to a value

(define (apply f x)

(eval (cddr (car f)) (cons (list (cadr (car f)) x) (cdr f))))

; read and parse stdin, then evaluate:

(display (eval (read) '())) (newline)

This code will read a program from stdin, parse it, evaluate it and print the result.

(It's 7 lines without the comments and blank lines.)

代碼將從文件中讀入程序、分析、求值最后打印值(這是一段沒有注釋和空白行的7行代碼)

Schema語言的read函數(shù)使得詞法分析和語法分析簡(jiǎn)單化。只要你想處于語法“平衡圓括號(hào)”(符號(hào)式)世界里。

(如果不想的話，你必須鉆研語法分析，你可以從我寫的一篇語法分析文章開始)

在Scheme語言中，read函數(shù)從文件獲取加括號(hào)的輸入并把它分析然后生成樹

函數(shù)eval 和 apply構(gòu)成了解釋器的內(nèi)核。即使我們使用的是Scheme語言，我們?nèi)越o出了函數(shù)概念上的“簽名”

eval : Expression * Environment -> Value

apply : Value * Value -> Value

Environment = Variable -> Value

Value = Closure

Closure = Lambda * Environment

eval函數(shù)將一個(gè)表達(dá)式和環(huán)境變量賦給一個(gè)值。表達(dá)式可以是一個(gè)變量、λ術(shù)語或者是一個(gè)應(yīng)用。

一個(gè)環(huán)境值是從變量到值的映射，用來定義一個(gè)開項(xiàng)的自由變量(開項(xiàng)用來存放出現(xiàn)的沒有綁定的變量)。想一下這個(gè)例子，表達(dá)式(λ x . z)是開項(xiàng)，因?yàn)槲覀儾恢纙是什么。

因?yàn)槲覀兪褂肧cheme語言標(biāo)準(zhǔn)(R5RS)，所以用聯(lián)合列表來定義環(huán)境值

閉項(xiàng)是一個(gè)函數(shù)的編碼，這個(gè)函數(shù)使用定義自由變量的環(huán)境值來匹配lambda 表達(dá)式來。換句話說來說，閉項(xiàng)關(guān)閉了一個(gè)開項(xiàng)

Racket中有一種更簡(jiǎn)潔的實(shí)現(xiàn)

Racket是Scheme的一種方言，功能齊備強(qiáng)大。它提供了一個(gè)整頓解釋器的匹配構(gòu)造機(jī)制。

#lang racket

; bring in the match library:

(require racket/match)

; eval matches on the type of expression:

(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 destructures the function with a match too:

(define (apply f x) (match f

[`(closure (λ ,v . ,body) ,env)

(eval body (cons `(,v ,x) env))]))

; read in, parse and evaluate:

(display (eval (read) '())) (newline)

這一種更加龐大，但是理解起來也更容易、更簡(jiǎn)單

一門更加龐大的語言

λ演算是一門極小的語言。盡管如此，解釋器eval/apply的設(shè)計(jì)可以升級(jí)到更加龐大的語言。

例如，用大約100行的代碼，我們可以為Scheme本身相當(dāng)大的一個(gè)子集實(shí)現(xiàn)解釋器

考慮一門含有不同表達(dá)式分類的語言：

變量引用：除x,foo,save_file

數(shù)值和布爾類型的常量：除300,3.14，#f。

原語操作：除+，-，<=

條件語句：(if condition if-true if-false)

變量綁定：(let ((var value) ...) body-expr).

遞歸綁定：(letrec ((var value) ...) body-expr)

變量變化：(set! var value)

序列化：(begin do-this then-this).

現(xiàn)在在語言中添加三種高級(jí)形式：

函數(shù)定義：(define (proc-name var …) expr).

全局定義：(define var expr)

高級(jí)表達(dá)式：expr

下面是完整的解釋器，包含測(cè)試代碼和測(cè)試用例：

#lang racket

(require racket/match)

;; Evaluation toggles between eval and apply.

; eval dispatches on the type of expression:

(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))]))

; a handy wrapper for 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*)))

; applies a procedure to arguments:

(define (apply-proc f values)

(match f

[`(closure (lambda ,vs ,body) ,env)

; =&gt;

(eval body (env-extend* env vs values))]

[`(primitive ,p)

; =&gt;

(apply p values)]))

;; Environments map variables to mutable cells

;; containing values.

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

; empty environment:

(define (env-empty) (hash))

; initial environment, with bindings for primitives:

(define (env-initial)

(env-extend*

(env-empty)

'(+ - / * &lt;= void display newline)

(map (lambda (s) (list 'primitive s))

`(,+ ,- ,/ ,* ,&lt;= ,void ,display ,newline))))

; looks up a value:

(define (env-lookup env var)

(cell-value (hash-ref env var)))

; sets a value in an environment:

(define (env-set! env var value)

(set-cell-value! (hash-ref env var) value))

; extends an environment with several bindings:

(define (env-extend* env vars values)

(match `(,vars ,values)

[`((,v . ,vars) (,val . ,values))

; =&gt;

(env-extend* (hash-set env v (make-cell val)) vars values)]

[`(() ())

; =&gt;

env]))

; mutates an environment with several assignments:

(define (env-set!* env vars values)

(match `(,vars ,values)

[`((,v . ,vars) (,val . ,values))

; =&gt;

(begin

(env-set! env v val)

(env-set!* env vars values))]

[`(() ())

; =&gt;

(void)]))

;; Evaluation tests.

; define new syntax to make tests look prettier:

(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 (&lt;= 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)

;; Programs are translated into a single letrec expression.

(define (define-&gt;binding define)

(match define

[`(define (,f . ,formals) ,body)

; =&gt;

`(,f (lambda ,formals ,body))]

[`(define ,v ,value)

; =&gt;

`(,v ,value)]

[else

; =&gt;

`(,(gensym) ,define)]))

(define (transform-top-level defines)

`(letrec ,(map define-&gt;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)))))

; read in a program, and evaluate:

(eval-program (read-all))

更多信息請(qǐng)查看IT技術(shù)專欄