编程代码大全(想学程序员又是零基础)

大家好，我是讯享网，很高兴认识大家。

这篇文章最初发表在Matt may的个人博客上。

本文介绍了各种解释器的实现。通过修改最后一个解释器，您应该能够快速测试关于编程语言的新想法。如果您想要一种具有不同语法的语言，您可以构建一个解析器并转储s表达式。这样，你就可以清楚地将语法设计和语义设计分开。

实现一门编程语言是任何程序员都不应该错过的经历；这个过程可以培养你对计算的深刻理解，很好玩。

本文直奔本质，将整个过程概括为:一个函数式(但图灵等价)编程语言的7行解释器，实现只需要3分钟左右。

这个7行解释器展示了存在于许多解释器中的可扩展架构——eval/apply在计算机程序的结构和解释中的设计模式:

本文中有三种语言实现:

一个使用 Scheme 耗时 3 分钟实现的 7 行解释器；使用Racket重新实现；一个耗时“一下午”实现的 100 行解释器，实现了顶层绑定形式、显式递归、副作用、高阶函数等功能。如果想要实现一门功能更丰富的语言，那么最后一个解释器是一个不错的起点。一门小语言（但图灵等价）

最容易实现的编程语言是名为lambda calculus的极简高阶函数式编程语言。

实际上，λ演算是所有主要函数式语言的核心——Haskell、Scheme和ML——但它也存在于JavaScript、Python和Ruby中。它甚至隐藏在Java中。我想知道你是否知道在哪里能找到它。

λ演算简史

Allonzot Church在1929年发展了λ微积分。

那时候还不叫编程语言，因为那时候还没有电脑；没有什么是可以被“编程”的。

它实际上只是一个函数推理的数学符号。好在Allonzot Church有个博士生叫alan turing。

艾伦·图灵定义了图灵机，成为第一个公认的通用计算机定义。

很快发现，λ演算和图灵机是等价的:任何可以用λ演算描述的函数都可以在图灵机上实现，任何可以在图灵机上实现的函数都可以用λ演算描述。

值得注意的是，λ演算中只有三种表达式:变量引用、匿名函数和函数调用。

匿名函数

匿名函数用“λ-点”符号编写，如下所示:

(λ v. e)复制代码

该函数接受参数V并返回值e。如果用JavaScript编写，上述代码相当于:

函数(v){ return e；}复制代码

函数调用

编写函数调用时，两个表达式是相邻的:

复制代码

JavaScript(或任何其他语言)编写如下:

F(e)复制代码

示例

编写返回参数的标识函数，如下所示:

(λ x. x)复制代码

我们可以将恒等函数应用于恒等函数:

((λ x. x) (λ a. a))复制代码

(当然，返回也是一个身份函数。)下面这个节目比较有意思:

(((λ F. (λ X. (F X))) (λ A.A.)) (λ B.B .))复制代码

你能理解它做了什么吗？

这到底是怎样的一种“编程”语言？

乍一看，这种简单的语言似乎缺乏递归和迭代，更不用说数值、布尔值、条件、数据结构等其他东西了。这种语言怎么可能通用？

λ的演算通过两个最酷的编程黑科技达到图灵等价:Church编码和Y combinator。

我已经写过一篇关于Y combinator的文章，也写过一篇关于教会编码的文章。不过，如果你不想看这些文章也没关系。我只需要一个程序让你相信λ演算的功能远远超出你的预期:

((λ f. (f f)) (λ f. (f f))复制代码。

这个看似无害的程序叫做Omega。如果你尝试执行它，你会发现它不会停止！看看能不能找出原因。

实现λ演算

下面是一个7行λ演算解释器，用R5RS方案实现需要3分钟。在技术上(下面解释)，它是一个基于环境的指示性解释器。

；Eval将表达式和环境转换为值(define (eval e env) (cond (symbol？e)(cadr(assq e env))((eq？(汽车e)& # 39；λ)(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)(cdrf)))；从stdin中读取并解析，然后求值:(display(eval(read)& # 39；()))(换行符)复制代码

这段代码将从stdin中读取一个程序，解析它，评估它并打印结果。(去掉注释和空行，它只有7行)。Scheme的read功能简化了词法分析和解析——只要你愿意生活在“平衡括号”(即s表达式)的语法世界里。(如果不愿意，一定要认真学习解析中的词法分析；可以从我的一篇关于词法分析的文章开始)。在Scheme中，read从stdin获取带括号的输入，并将其解析为一个树。

Eval和apply函数构成了解释器的核心。虽然它在Scheme中，但我们可以给这些函数一些概念性的“签名”:

eval:Expression * Environment->；应用值:值*值-& gt；价值环境=变量-& gt；Value = closure closure = lambda *环境复制代码

eval函数接收一个表达式和一个环境，然后将其转换为一个值。表达式可以是变量、lambda项或应用程序。环境是从变量到值的映射，用于定义开放项的自由变量。(开放项是变量的未绑定出现。)例如，考虑表达式(λ x. z)。这个项目是开放的，因为我们不知道z是什么。

由于使用了R5RS方案，我们可以使用关联列表来定义环境。

闭包是一个函数的代码，它将一个(可能是开放的)lambda表达式与一个环境配对，以定义它的自由变量。换句话说，闭包封闭了一个打开的项目。

使用 Racket 的实现更简洁

球拍是计划的一种方言。它功能全，能把事情做好。球拍提供了一个可以清理解释器的匹配结构，如下:

#球拍语言；介绍搭配库:(需要球拍/搭配)；Eval匹配表达式类型:(define (evalexpenv) (matchexp [`(，f，e)(apply(eval f env)(eval e env))][`(λ，v，e )` (closure，exp，env)] [(？符号？)(cadr(assq exp env))]))；Apply用match析构函数:(define(apply f x)(match f[`(closure(λ，v .，body)，env) (evalbody (cons `(，v，x)env))))；读取、解析、评估:(display(eval(read)& # 39；()))(换行符)复制代码

这段代码更多，但更简洁，更容易理解。

一门更大的语言

λ微积分是一门很小的语言。即便如此，其解释器的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)。现在，为这门语言添加 3 个顶层形式：函数定义：(define (proc-name var …) expr)。全局定义：(define var expr)。顶层表达式：expr。下面是完整的解释器，其中包括测试工具和测试用例：

#语言球拍(需要球拍/比赛)；；计算在eval和apply之间切换。；求值分派表达式类型:(define (eval exp env) (match exp [(？符号？)(env-lookup env exp)] [(？号码？)exp] [(？布尔？)exp] [`(if，ec，et，ef)(if(eval EC env)(eval et env)(eval ef env))][`(let rec，binds，eb) (eval-letrec绑定eb env)] [`(let，binds，eb) (eval-let绑定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))；用于letrec的eval:(define(eval-let rec 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))；= & gt(eval body(env-extend * env vs values))][`(primitive，p)；= & gt(应用p值)])；；将环境变量映射到包含值的可变单元格。(define-struct单元格([value #:mutable])；Clear 空环境:(define(env-empty)(hash))；初始化环境并绑定基本操作:(define(env-initial)(env-extend *(env-empty)& # 39；(+-/* & lt；= void display newline)(map(lambda(s)(list & # 39；primitive s))`(，+，-，/，*，& lt=，void，display，newline)))))；找一个值:(define(env-lookup env var)(cell-value(hash-ref env var)))；在环境中设置一个值:(define (env-set！环境变量值)(设置单元格值！(hash-ref环境变量值))；通过多个绑定扩展环境:(define(env-extend * env vars values)(match `(，vars，values) [`(，v .，vars)(，val。，值))；= & gt(env-extend *(hash-set env v(make-cell val))vars values)][`(()())；= & gtenv]))；通过多重赋值改变环境:(define (env-set！*环境变量值) (match `(，变量，值)[`((，v .，变量)(，值。，值))；= & gt(begin (env-set！环境v值)(环境集！* env vars values))][`(()())；= & gt(void)])；；计算测试。；定义新的语法让测试看起来更漂亮:(define-syntax test-eval(syntax-rules(= = =)][(_ program = = = value)(let((result(eval(quote program)(env-initial)))(when(not(not)program value))(error & # 34；测试失败！”)))))))(test-eval((lambda(x)(+3 4))20)= = = 7)(test-eval(let rec((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)；；该程序被翻译成letrec表达式。(定义(定义-& gt；binding define)(匹配定义[`(define(，f .，formals)，body)；= & gt`(，f (lambda，formals，body))] [`(define，v，value)；= & gt`(，v，value)][else；= & gt`(，(gensym)，define)])(define(transform-顶层定义)`( letrec，(map define-& gt；绑定定义)(void)))(define (eval-program程序)(eval(transform-顶层程序)(env-initial)))(define(read-all)(let((next(read)))(if(eof-object？接下来)& # 39；()(cons next(read-all))))))；读入一个程序并计算:(eval-program (read-all))复制代码

下载源代码请点击https://matt . mighty . net/articles/implementing-a-programming-lang/minilang . rkt？accessToken = eyjhbgcioijuzi 1 niismtpzci 6 imrlzmf 1 bhqil CJ 0 exaioijkv 1 qifq . eyjhdwqioijhy nlc 3 nfcmvzb 3 vyy 2 uilcjehaioj 2 NTU 0n tmzmzasimzpbgvhvuleijoibg 9 xzvcy rxl d 0 hkskxbiisimlhdci 6 mty 1 ntq 1 mzazmcwidxnlcklkijoymdqxota 5 MH 0。NV 5 uyu udcujnt 7 c 0 KIA PSE 0g 0 f4k 9 ed 26 RLL 2 bu 5 RPG 4

结语

通过修改最后一个解释器，您应该能够快速测试关于编程语言的新想法。

如果您想要一种具有不同语法的语言，您可以构建一个解析器并转储s表达式。这样，你就可以清楚地将语法设计和语义设计分开。

查看英文原文:

https://matt . may . net/articles/implementing-a-programming-language？accessToken = eyjhbgcioijuzi 1 niismtpzci 6 imrlzmf 1 bhqil CJ 0 exaioijkv 1 qifq . eyjhdwqioijhy nlc 3 nfcmvzb 3 vyy 2 uilcjehaioj 2 NTU 0n tmzmzasimzpbgvhvuleijoibg 9 xzvcy rxl d 0 hkskxbiisimlhdci 6 mty 1 ntq 1 mzazmcwidxnlcklkijoymdqxota 5 MH 0。NV 5 uyu udcujnt 7 c 0 KIA PSE 0g 0 f4k 9 ed 26 RLL 2 bu 5 RPG 4