實現一門編程語言對任何程序員來說都是值得擁有的經驗，因為它能加深你對計算原理的理解，并且還很有趣。
在這篇文章中，我已經讓整個過程回歸到它的本質：為一種函數式（圖靈等價）編程語言設計7行代碼的解釋器。大概只需要3分鐘就能實現
這個7行代碼的解釋器展示了在眾多解釋器中同時存在的一個可升級的體系結構–eval/apply設計模式。Structure and Interpretation of Computer Programs這本書提到過該模式。
在這篇文章中總計有三門語言的實現：
一個是scheme語言的7行，3分鐘實現的解釋器
一個是Racket語言的重實現
最后一個是100行、“1-afternoon”解釋器，它實現了高級綁定形式、顯示遞歸、額外作用、高階函數式等等
對于掌握一門更豐富的語言來說，最后一個解釋器是一個好起點
一個小型(圖靈機等價)語言
最容易實現的一門編程語言是一個叫做λ運算的極簡單、高階函數式編程語言
λ運算實際上存在于所有主要的功能性語言的內核中：Haskell, Scheme、 ML，但是它也存在于JavaScript、Python、Ruby中。它甚至隱藏在Java中，如果你知道到哪里去找它。
歷史簡介
1929年Alonzo Church開發出λ演算
在那時，lambda calculus不被叫做編程語言因為沒有計算機，所以沒有編程的概念。
它僅僅是一個推演函數的數學標記。
幸運的是，Alonzo Church有一個叫作艾倫·圖靈的哲學博士。
艾倫·圖靈定義了圖靈機，圖靈機成了第一個被接受的通用計算機定義
不久后發現lambda calculus和圖靈機是等價的：任何用λ演算描述的功能可以在圖靈機上實現；并且在圖靈機上實現的任何功能可以用λ演算描述
值得注意的是在lambda calculus中僅有三種表達式：變量引用，匿名函數、函數調用
匿名函數：
(λv.e)
匿名函數以”λ-.”標記開始，所以 (λ v . e)函數用來接收一個參數v并返回值e。
如果你用JavaScript編程，格式function (v) { return e ; }是相同的。
函數調用：
(fe)
函數調用用兩個臨近的表達式表示：(f e)
f(e)
在JavaScript中（或者其他任何語言），寫為f(e)
Examples
(λ x . x)
例如：
恒等函數（identity function），僅僅返回它的參數值，簡單地寫為(λ x . x)
((λ x . x) (λ a . a))
我們可以將這個恒等函數應用到一個恒等函數上：
((λ x . x) (λ a . a))（僅返回這個恒等函數本身）
(((λ f . (λ x . (f x))) (λ a . a)) (λ b . b))
這兒有一個更有趣的程序：
(((λ f . (λ x . (f x))) (λ a . a)) (λ b . b))
你能弄清楚它是干嘛的？
等一下！見鬼，這怎么算一門編程語言？
乍一看，這門簡單語言好像缺乏遞歸和迭代，更不用說數字、布爾值、條件語句、數據結構和剩余其他的。這樣的語言怎么可能成為通用的呢？
λ演算實現圖靈機-等價的方式是通過兩種最酷的方式：
邱奇編碼（Church encoding）和Y combinator（美國著名企業孵化器）
((λ f . (f f)) (λ f . (f f)))
我已經寫了兩篇關于Y combinator和邱奇編碼的文章。
但是，你如果不想讀它們的話，我可以明確的告訴你比起你期望的僅一個((λ f . (f f)) (λ f . (f f)))程序來說 有更多的 lambda calculus知識。
表面上開始的程序叫做Ω，如果你嘗試運行它的話，它不會終止（想一下你是否明白其中原因）
實現λ演算
下面是基于Scheme語言標準(R5RS)的7行、3分鐘λ演算解釋器。在術語中，它是一個依賴環境的指示解釋器
; 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函數使得詞法分析和語法分析簡單化。只要你想處于語法“平衡圓括號”(符號式)世界里。
(如果不想的話，你必須鉆研語法分析，你可以從我寫的一篇語法分析文章開始)
在Scheme語言中，read函數從文件獲取加括號的輸入并把它分析然后生成樹
函數eval 和 apply構成了解釋器的內核。即使我們使用的是Scheme語言，我們仍給出了函數概念上的“簽名”
eval : Expression * Environment -> Value
apply : Value * Value -> Value
Environment = Variable -> Value
Value = Closure
Closure = Lambda * Environment
eval函數將一個表達式和環境變量賦給一個值。表達式可以是一個變量、λ術語或者是一個應用。
一個環境值是從變量到值的映射，用來定義一個開項的自由變量(開項用來存放出現的沒有綁定的變量)。想一下這個例子，表達式(λ x . z)是開項，因為我們不知道z是什么。
因為我們使用Scheme語言標準(R5RS)，所以用聯合列表來定義環境值
閉項是一個函數的編碼，這個函數使用定義自由變量的環境值來匹配lambda 表達式來。換句話說來說，閉項關閉了一個開項
Racket中有一種更簡潔的實現
Racket是Scheme的一種方言，功能齊備強大。它提供了一個整頓解釋器的匹配構造機制。
#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)
這一種更加龐大，但是理解起來也更容易、更簡單
一門更加龐大的語言
λ演算是一門極小的語言。盡管如此，解釋器eval/apply的設計可以升級到更加龐大的語言。
例如，用大約100行的代碼，我們可以為Scheme本身相當大的一個子集實現解釋器
考慮一門含有不同表達式分類的語言：
變量引用：除x,foo,save_file
數值和布爾類型的常量：除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).
現在在語言中添加三種高級形式：
函數定義：(define (proc-name var …) expr).
全局定義：(define var expr)
高級表達式：expr
下面是完整的解釋器，包含測試代碼和測試用例：
#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)
; =>
(eval body (env-extend* env vs values))]
[`(primitive ,p)
; =>
(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)
'(+ - / * <= void display newline)
(map (lambda (s) (list 'primitive s))
`(,+ ,- ,/ ,* ,<= ,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))
; =>
(env-extend* (hash-set env v (make-cell val)) vars values)]
[`(() ())
; =>
env]))
; mutates an environment with several assignments:
(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)]))
;; 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 (<= 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->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)))))
; read in a program, and evaluate:
(eval-program (read-all))
更多信息請查看IT技術專欄
版權所有:易賢網
公眾號
事業單位
當前位置：
公考類
招聘類
各類考試